Contents

Sliding Window

Longest Substring Without Repeating Characters

int lengthOfLongestSubstring(string s) {
    vector<int> cnt(256, 0);
    int dup = 0, best = 0;
    
    for (int l = 0, r = 0; r < s.size(); ++r) {
        dup += (++cnt[(unsigned char)s[r]] == 2);
        
        while (dup > 0) {
            dup -= (--cnt[(unsigned char)s[l++]] == 1);
        }
        
        best = max(best, r - l + 1);
    }
    
    return best;
}

Minimum Window Substring

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    int start = 0, len = INT_MAX;
    
    while (right < s.size()) {
        char c = s[right++];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        
        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    
    return len == INT_MAX ? "" : s.substr(start, len);
}
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
76 Minimum Window Substring Link -
424 Longest Repeating Character Replacement Link -

Two Pointers

Valid Palindrome

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    
    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

Reverse String

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left++], s[right--]);
    }
}
ID Title Link Solution
5 Longest Palindromic Substring Link Solution
125 Valid Palindrome Link -
344 Reverse String Link Solution
647 Palindromic Substrings Link Solution

String Matching

KMP Algorithm

vector<int> buildKMP(string pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
    }
    
    return lps;
}

int kmpSearch(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> lps = buildKMP(pattern);
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        
        if (j == m) {
            return i - j; // Found at index i - j
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return -1;
}
ID Title Link Solution
28 Find the Index of the First Occurrence in a String Link -

String Manipulation

Group Anagrams

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (string& str : strs) {
        string key = str;
        sort(key.begin(), key.end());
        groups[key].push_back(str);
    }
    
    vector<vector<string>> result;
    for (auto& [key, values] : groups) {
        result.push_back(values);
    }
    
    return result;
}

Remove Duplicates

// Remove All Adjacent Duplicates
string removeDuplicates(string s) {
    string result;
    for (char c : s) {
        if (!result.empty() && result.back() == c) {
            result.pop_back();
        } else {
            result.push_back(c);
        }
    }
    return result;
}

// Remove All Adjacent Duplicates II (k duplicates)
string removeDuplicates(string s, int k) {
    vector<pair<char, int>> st;
    
    for (char c : s) {
        if (!st.empty() && st.back().first == c) {
            st.back().second++;
            if (st.back().second == k) {
                st.pop_back();
            }
        } else {
            st.push_back({c, 1});
        }
    }
    
    string result;
    for (auto& [c, count] : st) {
        result.append(count, c);
    }
    
    return result;
}
ID Title Link Solution
49 Group Anagrams Link Solution
1047 Remove All Adjacent Duplicates In String Link Solution
1209 Remove All Adjacent Duplicates in String II Link Solution

Parsing

Valid Word Abbreviation

bool validWordAbbreviation(string word, string abbr) {
    int i = 0, j = 0;
    int n = word.size(), m = abbr.size();
    
    while (i < n && j < m) {
        if (isdigit(abbr[j])) {
            if (abbr[j] == '0') return false; // Leading zero
            int num = 0;
            while (j < m && isdigit(abbr[j])) {
                num = num * 10 + (abbr[j] - '0');
                j++;
            }
            i += num;
        } else {
            if (word[i] != abbr[j]) return false;
            i++;
            j++;
        }
    }
    
    return i == n && j == m;
}

Decode String

string decodeString(string s) {
    stack<int> numStack;
    stack<string> strStack;
    string current;
    int num = 0;
    
    for (char c : s) {
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            numStack.push(num);
            strStack.push(current);
            num = 0;
            current = "";
        } else if (c == ']') {
            int repeat = numStack.top();
            numStack.pop();
            string temp = current;
            current = strStack.top();
            strStack.pop();
            while (repeat--) {
                current += temp;
            }
        } else {
            current += c;
        }
    }
    
    return current;
}
ID Title Link Solution
408 Valid Word Abbreviation Link Solution
394 Decode String Link Solution