String

substring() is O(n)

Palindrome

validate

https://leetcode.com/problems/valid-palindrome/description/ https://leetcode.com/problems/palindrome-partitioning/description/ https://leetcode.com/problems/palindrome-permutation/description/ https://leetcode.com/problems/find-the-closest-palindrome/description/

private boolean isPalindrome(String s, int l, int r) {
    if (l == r) return true;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

central extention

key: 1) no need 2d table 2) 2 rounds: 1st round, aba; 2nd round, abba https://leetcode.com/problems/longest-palindromic-substring https://leetcode.com/problems/palindromic-substrings/description/ https://leetcode.com/problems/palindrome-partitioning-ii/description/

// iterate string
for (int i = 0; i < s.length() - 1; i++) {
    expends(s, i, i);
    expends(s, i, i+1);
}
private String expends(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return s.substring(l+1, r);
}

dynamic programming

need 2d table https://leetcode.com/problems/longest-palindromic-subsequence/description/ https://leetcode.com/problems/longest-palindromic-substring https://leetcode.com/problems/palindromic-substrings/description/ https://leetcode.com/problems/count-different-palindromic-subsequences/description/ key: 2 pointers

for (int i = 0; i < n; i++) {
    for (int j = i; j >= 0; j--) {
        if (s.charAt(j) == s.charAt(i)) {
            dp[j][i] = j == i || j + 1 == i ? i - j + 1 : 2 + dp[j+1][i-1];
        } else {
            dp[j][i] = Math.max(dp[j+1][i], dp[j][i-1]);
        }
    }
}

anagram/permutation

map char:counts

https://leetcode.com/problems/valid-anagram https://leetcode.com/problems/group-anagrams https://leetcode.com/problems/find-all-anagrams-in-a-string https://leetcode.com/problems/permutation-in-string/description/ https://leetcode.com/problems/find-anagram-mappings

String & word dict

lookup words from string in dict:

https://leetcode.com/problems/word-ladder/description/ https://leetcode.com/problems/word-ladder-ii/description/ https://leetcode.com/problems/word-break/description/

lookup words from dict in string:

https://leetcode.com/problems/add-bold-tag-in-string/description/

            for (String w : dict) {
                if (s.startsWith(w, i)) {
                    len = Math.max(len, w.length());
                }
            }