Minimal, copy-paste C++ for sliding window, two pointers, string matching, manipulation, and parsing. See also Arrays & Strings for KMP and rolling hash.
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--]);
}
}
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;
}
| ID |
Title |
Link |
Solution |
| 49 |
Group Anagrams |
Link |
- |
| 249 |
Group Shifted Strings |
Link |
Solution |
| 893 |
Groups of Special-Equivalent Strings |
Link |
Solution |
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;
}
Run-Length Encoding
// Two-pointer grouping for consecutive runs
string runLengthEncode(const string& s) {
string result;
for (int j = 0, k = 0; j < (int)s.size(); j = k) {
while (k < (int)s.size() && s[k] == s[j]) k++;
result += to_string(k - j) + s[j];
}
return result;
}
| ID |
Title |
Link |
Solution |
| 38 |
Count and Say |
Link |
Solution |
| 443 |
String Compression |
Link |
- |
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;
}
More templates