String

12. Valid Palindrome

class Solution {
public:
    bool isPalindrome(string s) {
        string trimmed;
        for (char c : s) {
            if (isalnum(c)) {
                trimmed += tolower(c);
            }
        }
        string reversed = trimmed;
        std::reverse(reversed.begin(), reversed.end());
        return trimmed == reversed;
    }
};

class Solution {
    public boolean isPalindrome(String s) {
        String trimmed = "";
        String lower = s.toLowerCase();
        for (char c : lower.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                trimmed += c;
            }
        }
        String reversed = new StringBuilder(trimmed).reverse().toString();
        return trimmed.equals(reversed);
    }
}

13. 42. Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> v(26, 0);
        for (char c : s) {
            v[c-'a']++;
        }
        for (char c : t) {
            v[c-'a']--;
        }
        for (int i : v) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
};

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] v = new int[26];
        for (char c : s.toCharArray()) {
            v[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            v[c - 'a']--;
        }
        for (int i : v) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

14. 3. Longest Substring Without Repeating Characters

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0, left = 0, right = 0;
        HashSet<Character> cache = new HashSet<>();
        for (;right < s.length(); right++) {
            char c = s.charAt(right);
            if (cache.contains(c)) {
                do {
                    char l = s.charAt(left);
                    cache.remove(l);
                    left++;
                } while (cache.contains(c));
                cache.add(c);
            } else {
                cache.add(c);
                maxLength = Math.max(maxLength, cache.size());
            }
        }
        return maxLength;
    }
}

# https://leetcode.com/problems/minimum-window-substring/solutions/
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        unordered_set<char> charSet;
        int left = 0;

        for (int right = 0; right < n; right++) {
            if (charSet.count(s[right]) == 0) {
                charSet.insert(s[right]);
                maxLength = max(maxLength, right - left + 1);
            } else {
                while (charSet.count(s[right])) {
                    charSet.erase(s[left]);
                    left++;
                }
                charSet.insert(s[right]);
            }
        }
        return maxLength;
    }
};

15. Longest Palindrome

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> map;
        for (char &c : s) {
            map[c]++;
        }
        int result = 0;
        bool flag = false;
        for (auto& p : map) {
            if (p.second % 2 == 0) {
                result += p.second;
            } else {
                result += p.second - 1;
                flag = true;
            }
        }
        return (flag) ? result + 1 : result;
    }
};

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int result = 0;
        boolean flag = false;
        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue() % 2 == 0) {
                result += e.getValue();
            } else {
                result += e.getValue() - 1;
                flag = true;
            }
        }
        return flag ? result + 1 : result;
    }
}

16. 76. Minimum Window Substring

// https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems/

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> v(128, 0);
        for (auto c : t) v[c]++;
        int counter = t.size(), begin = 0, end = 0, d = INT_MAX, head = 0;
        while (end < s.size()) {
            if (v[s[end++]]-- > 0) counter--;
            while (counter == 0) {
                if (end - begin < d) d = end - (head = begin);
                if (v[s[begin++]]++ == 0) counter++;
            }
        }
        return d == INT_MAX ? "" : s.substr(head, d);
    }
};

class Solution {
    public String minWindow(String s, String t) {
        int[] v = new int[128];
        int counter = t.length(), begin = 0, end = 0, d = Integer.MAX_VALUE, head = 0;

        for (char c : t.toCharArray()) {
            v[c]++;
        }
        
        char[] sa = s.toCharArray();
        while (end < sa.length) {
            if (v[sa[end++]]-- > 0) {
                counter--;
            }
            while (counter == 0) {
                if (end - begin < d) {
                    d = end - begin;
                    head = begin;
                }
                if (v[sa[begin++]]++ == 0) {
                    counter++;
                }
            }
        }
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head+d);
    }
}

17. 8. String to Integer (atoi)

class Solution {
public:
    int myAtoi(string s) {
        int i = 0;
        int sign = 1; 
        long ans = 0;
        while (i < s.length() && s[i] == ' ') {
            i++;
        }
        if (s[i] == '-') {
            sign = -1;
            i++;
        } else if (s[i] == '+') {
            i++;
        }
        while (i < s.length()) {
            if (s[i] >= '0' && s[i] <= '9') {
                ans = ans*10 + (s[i] - '0');
                if (ans > INT_MAX && sign == -1) {
                    return INT_MIN;
                } else if (ans > INT_MAX && sign == 1) {
                    return INT_MAX;
                }
                i++;
            } else {
                return ans * sign;
            }
        }
        return ans * sign;
    }
};

18. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/solutions/4212564/beats-96-49-5-different-approaches-brute-force-eac-dp-ma-recursion/

class Solution {
    public String longestPalindrome(String s) {
        return solution5(s);
    }

    // [Manacher Algorithm](https://www.youtube.com/watch?v=h_fSaWvxD2Y)
    // https://www.youtube.com/watch?v=Dg0EP43jTXg
    private String solution1(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }   
        char[] chars = s.toCharArray();
        char[] newChars = toNewCharArray(chars);
        int[] results = new int[newChars.length];
        int center = 0;
        int right = 0;
        for (int i = 1; i < newChars.length - 1; i++) {
            int i_mirror = 2*center-i;
            if (i < right) {
                results[i] = Math.min(right - i, results[i_mirror]);
            }
            while(newChars[i+results[i]+1] == newChars[i-results[i]-1]) {
                results[i]++;
            }
            if (i+results[i] > right) {
                center = i;
                right = i+ results[i];
            }
        }

        int maxLength = 0;
        int maxIndex = 0;
        for (int i = 1; i < newChars.length - 1; i++) {
            if (results[i] > maxLength) {
                maxLength = results[i];
                maxIndex = i;
            }
        }

        int start = (maxIndex - maxLength) / 2;
        //return s.substring(start, start+maxLength);
        return new String(chars, start, maxLength);
    }

    private char[] toNewCharArray(char[] chars) {
        char[] newChars = new char[chars.length*2+3];
        int index = 0;
        newChars[index++] = '^';
        for (int i = 0; i < chars.length; i++) {
            newChars[index++] = '#';
            newChars[index++] = chars[i];
        }
        newChars[index++] = '#';
        newChars[index] = '$';
        return newChars;
    }

    // brute force
    private String solution2(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }  
        int n = s.length();
        int maxLen = 0;
        int maxStart = 0;
        for (int start = 0; start < n; start++) {
            // note here is len = maxLen+1 > maxlen for sure, and end <= n
            for (int end = start+maxLen; end < n; end++) {
                String sub = s.substring(start, end+1);
                if (isPalindrom(sub)) {
                    maxLen = sub.length();
                    maxStart = start;
                }
            }
        }
        return s.substring(maxStart, maxStart+maxLen);
    }

    private boolean isPalindrom(String s) {
        String reversed = new StringBuilder(s).reverse().toString();
        return reversed.equals(s);
    }

    // recursive
    private String solution3(String s) {
        if (isPalindrom(s)) {
            return s;
        }

        String left = solution3(s.substring(0, s.length()-1));
        String right = solution3(s.substring(1));

        if (left.length() > right.length()) {
            return left;
        } else {
            return right;
        }
    }

    // dp
    private String solution4(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }   
        int n = s.length();
        int maxLen = 1;
        int maxStart = 0;
        boolean[][] dp = new boolean[n][n];
        
        for (int end = 0; end < s.length(); end++) {
            dp[end][end] = true;
            for (int start = 0; start < end; start++) {
                if (s.charAt(start) == s.charAt(end) && (end - start <= 2 || dp[start+1][end-1])) {
                    dp[start][end] = true;
                    if (end - start + 1 > maxLen) {
                        maxLen = end - start + 1;
                        maxStart = start;
                    }
                }
            }
        }
        return s.substring(maxStart, maxStart+maxLen);
    }

    // expand from middle
    private String solution5(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        String maxStr = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String odd = expandingFromCenter(s, i, i);
            String even = expandingFromCenter(s, i, i+1);
            if (odd.length() > maxStr.length()) {
                maxStr = odd;
            }
            if (even.length() > maxStr.length()) {
                maxStr = even;
            }
        }
        return maxStr;
    }

    private String expandingFromCenter(String s, int left, int right) {
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left+1, right);
    }
}

19. Find All Anagrams in a String

class Solution {
private:
    static const int SIZE = 26;
    bool isAnagram(int (&sa)[], int (&pa)[]) {
        for (int i = 0; i < SIZE; i++) {
            if (sa[i] != pa[i]) {
                return false;
            }
        }
        return true;
    }

public:
    vector<int> findAnagrams(string s, string p) {
        int sa[SIZE] = {0};
        int pa[SIZE] = {0};

        for (int i = 0; i < p.length(); i++) {
            ++pa[p[i]-'a'];
        }
        
        vector<int> res;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            ++sa[s[right]-'a'];
            if (right-left+1 < p.length()) {
                continue;
            } else {
                if (isAnagram(sa, pa)) {
                    res.push_back(left);
                }
                --sa[s[left]-'a'];
                left++;
            }
        }
        return res;
    }
};

class Solution {
    private static final int SIZE = 26;

    public List<Integer> findAnagrams(String s, String p) {
        int[] sa = new int[SIZE];
        int[] pa = new int[SIZE];

        for (int i = 0; i < p.length(); i++) {
            pa[p.charAt(i) - 'a']++;
        }
        
        List<Integer> res = new LinkedList<>();
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            sa[s.charAt(right)-'a']++;
            if (right-left+1 < p.length()) {
                continue;
            } else {
                if (isAnagram(sa, pa)) {
                    res.add(left);
                }
                sa[s.charAt(left)-'a']--;
                left++;
            }
        }
        return res;
    }

    private boolean isAnagram(int[] sa, int[] pa) {
        for (int i = 0; i < SIZE; i++) {
            if (sa[i] != pa[i]) {
                return false;
            }
        }
        return true;
    }
}

Sort with Dictionary

• Example 1

  • Dictionary: "CDEBA"

  • Input: "ABC"

  • Output: "CBA"

string test(string& input, string& dictionary) {
    int tmp[dictionary.length()];
    std::fill(tmp, tmp+dictionary.length(), 0);
    
    for (auto& c : input) {
        size_t p = dictionary.find(c);
        if (p != string::npos) {
            tmp[p]++;
        }
    }
    string result;
    for (int i = 0; i < dictionary.length(); i++) {
        while (tmp[i] > 0) {
            result += dictionary[i];
            tmp[i]--;
        }
    }
    return result;
}