<commit_before># https://leetcode.com/problems/longest-palindromic-subsequence/

"""
Dynamic Programming

We have the following cases:
LPS[i, i] = 1 ; every single char is a palindrome of itself
LPS[i, j] = 2 if j=i+1 ; sequence only has 2 characters
LPS[i, j] = 2 + LPS[i+1, j-1] if first and last chars the same
LPS[i, j] = max{LPS[i+1,j], LPS[i, j-1]} if first and last chars aren't same

Keep a memo_table where memo_table[i][j] is defined as the length of the<commit_msg>solved n^2 solution using a 2D memotable.<commit_after># https://leetcode.com/problems/longest-palindromic-subsequence/

"""
Dynamic Programming

Go through the array keeping two pointers to denote begin and end of the subarray.
Do this for subarrays size 2, 3, ... ,N

For each of the subarrays we have:

We have the following cases:
LPS[i, i] = 1 ; every single char is a palindrome of itself
LPS[i, j] = 2 if j=i+1 ; sequence only has 2 characters
LPS[i, j] = 2 + LPS[i+1, j-1] if first and last chars the same
LPS[i, j] = max{LPS[i+1,j], LPS[i, j-1]} if first and last chars aren't same

Keep a memo_table where memo_table[i][j] is defined as the length of the
{'fraction_non_alphanumeric': 0.11228070175438597, 'fraction_numerical': 0.01929824561403509, 'mean_word_length': 4.258064516129032, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1456572', 'n_tokens_mistral': 435, 'n_tokens_neox': 406, 'n_words': 167}