String Matching and Pattern Search

1. Longest Substring Without Repeating Characters

Technique Strategy Data Structure Time Complexity
Sliding Window Expand right, shrink left when duplicate found HashSet or HashMap for tracking O(n)
HashMap Optimization Store last seen index, jump left pointer Map: char → last index O(n)
Array Index Use array for ASCII characters (256 size) lastSeen[128] or [256] O(n)

Example: Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // If char seen and within current window
    if (seen.has(char) && seen.get(char) >= left) {
      // Move left pointer past the previous occurrence
      left = seen.get(char) + 1;
    }
    
    // Update last seen position
    seen.set(char, right);
    
    // Update max length
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("bbbbb")); // 1 ("b")
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

// Trace for "abcabcbb":
// right=0, char='a': seen={a:0}, left=0, len=1
// right=1, char='b': seen={a:0,b:1}, left=0, len=2
// right=2, char='c': seen={a:0,b:1,c:2}, left=0, len=3
// right=3, char='a': seen at 0, left=1, len=3
// right=4, char='b': seen at 1, left=2, len=3
// ...

Example: Alternative Using Set

function lengthOfLongestSubstringSet(s) {
  const window = new Set();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Shrink window while duplicate exists
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }
    
    window.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

// Using array for ASCII (faster for small character sets)
function lengthOfLongestSubstringArray(s) {
  const lastSeen = new Array(128).fill(-1);
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const charCode = s.charCodeAt(right);
    
    // If char seen within current window
    if (lastSeen[charCode] >= left) {
      left = lastSeen[charCode] + 1;
    }
    
    lastSeen[charCode] = right;
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}
Note: The HashMap optimization jumps left directly to index + 1 of duplicate character, avoiding the need to remove characters one-by-one. This maintains O(n) with only one pass.

2. Longest Palindromic Substring (Manacher's Algorithm)

Algorithm Approach Key Idea Complexity
Expand Around Center Try each position as center, expand outward Handle odd/even length separately O(n²)
Dynamic Programming dp[i][j] = is s[i..j] palindrome Build from length 1 to n O(n²)
Manacher's Algorithm Use previously computed palindromes Mirror property + special characters O(n)

Example: Expand Around Center

function longestPalindrome(s) {
  if (!s || s.length < 1) return "";
  
  let start = 0, maxLen = 0;
  
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    // Return length of palindrome
    return right - left - 1;
  }
  
  for (let i = 0; i < s.length; i++) {
    // Odd length palindrome (single center)
    const len1 = expandAroundCenter(i, i);
    
    // Even length palindrome (two centers)
    const len2 = expandAroundCenter(i, i + 1);
    
    const len = Math.max(len1, len2);
    
    if (len > maxLen) {
      maxLen = len;
      // Calculate start position
      start = i - Math.floor((len - 1) / 2);
    }
  }
  
  return s.substring(start, start + maxLen);
}

console.log(longestPalindrome("babad")); // "bab" or "aba"
console.log(longestPalindrome("cbbd")); // "bb"

// Why expand around center works:
// "racecar": center at 'e' → expands to full string
// "abba": center between 'b' and 'b' → expands to full string

Example: Manacher's Algorithm (Linear Time)

function longestPalindromeManacher(s) {
  if (!s) return "";
  
  // Transform string: "abc" → "^#a#b#c#$"
  // ^ and $ are sentinels to avoid boundary checks
  let T = "^";
  for (const char of s) {
    T += "#" + char;
  }
  T += "#$";
  
  const n = T.length;
  const P = new Array(n).fill(0); // P[i] = radius of palindrome centered at i
  let center = 0, right = 0;
  
  for (let i = 1; i < n - 1; i++) {
    // Mirror of i with respect to center
    const mirror = 2 * center - i;
    
    // If i is within right boundary, use mirror's value
    if (i < right) {
      P[i] = Math.min(right - i, P[mirror]);
    }
    
    // Try to expand palindrome centered at i
    while (T[i + P[i] + 1] === T[i - P[i] - 1]) {
      P[i]++;
    }
    
    // If palindrome centered at i extends past right, update center
    if (i + P[i] > right) {
      center = i;
      right = i + P[i];
    }
  }
  
  // Find the longest palindrome
  let maxLen = 0;
  let centerIndex = 0;
  for (let i = 1; i < n - 1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  
  // Extract the longest palindrome from original string
  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}

console.log(longestPalindromeManacher("babad")); // "bab" or "aba"

// Manacher's key insight:
// Use symmetry - palindrome's left half mirrors right half
// If position i is inside palindrome centered at c,
// then P[i] is at least min(P[mirror], right - i)
Note: Manacher's algorithm uses mirror property of palindromes and adds special characters (#) to handle both odd and even length palindromes uniformly. Achieves O(n) by avoiding redundant comparisons.

3. Minimum Window Substring (Sliding Window)

Technique Strategy Tracking Complexity
Two Pointers Expand right until valid, shrink left while valid Count required vs found characters O(n + m)
Character Frequency Map to track required and current counts Compare frequencies for validity O(n)
Formed Counter Count how many unique chars meet requirement formed === required → valid window O(n)

Example: Minimum Window Substring

function minWindow(s, t) {
  if (!s || !t || s.length < t.length) return "";
  
  // Count characters in t
  const tCount = new Map();
  for (const char of t) {
    tCount.set(char, (tCount.get(char) || 0) + 1);
  }
  
  const required = tCount.size; // Unique characters needed
  let formed = 0; // Unique characters in current window with desired frequency
  
  const windowCount = new Map();
  let left = 0;
  let minLen = Infinity;
  let minStart = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    windowCount.set(char, (windowCount.get(char) || 0) + 1);
    
    // Check if this character's frequency matches requirement
    if (tCount.has(char) && windowCount.get(char) === tCount.get(char)) {
      formed++;
    }
    
    // Try to shrink window while it's valid
    while (formed === required && left <= right) {
      // Update result if this window is smaller
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      
      // Remove leftmost character
      const leftChar = s[left];
      windowCount.set(leftChar, windowCount.get(leftChar) - 1);
      
      if (tCount.has(leftChar) && windowCount.get(leftChar) < tCount.get(leftChar)) {
        formed--;
      }
      
      left++;
    }
  }
  
  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "a")); // "a"
console.log(minWindow("a", "aa")); // ""

// Trace for "ADOBECODEBANC", "ABC":
// Need: {A:1, B:1, C:1}
// Window expands to "ADOBEC" - valid, try shrink
// Window "DOBEC" - invalid (no A)
// Continue expanding to "ODEBANC" - valid
// Final answer: "BANC"

Example: Simplified Version with Character Array

function minWindowSimplified(s, t) {
  const tFreq = {};
  for (const char of t) {
    tFreq[char] = (tFreq[char] || 0) + 1;
  }
  
  let required = Object.keys(tFreq).length;
  let formed = 0;
  const windowFreq = {};
  
  let left = 0;
  let result = "";
  let minLen = Infinity;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    windowFreq[char] = (windowFreq[char] || 0) + 1;
    
    if (tFreq[char] && windowFreq[char] === tFreq[char]) {
      formed++;
    }
    
    while (formed === required) {
      // Update result
      const windowSize = right - left + 1;
      if (windowSize < minLen) {
        minLen = windowSize;
        result = s.substring(left, right + 1);
      }
      
      // Shrink
      const leftChar = s[left];
      if (tFreq[leftChar] && windowFreq[leftChar] === tFreq[leftChar]) {
        formed--;
      }
      windowFreq[leftChar]--;
      left++;
    }
  }
  
  return result;
}

// Variation: Find all start indices
function findSubstring(s, words) {
  if (!s || !words || words.length === 0) return [];
  
  const wordLen = words[0].length;
  const totalLen = wordLen * words.length;
  const wordCount = {};
  
  for (const word of words) {
    wordCount[word] = (wordCount[word] || 0) + 1;
  }
  
  const result = [];
  
  for (let i = 0; i <= s.length - totalLen; i++) {
    const seen = {};
    let j = 0;
    
    while (j < words.length) {
      const wordStart = i + j * wordLen;
      const word = s.substring(wordStart, wordStart + wordLen);
      
      if (!wordCount[word]) break;
      
      seen[word] = (seen[word] || 0) + 1;
      if (seen[word] > wordCount[word]) break;
      
      j++;
    }
    
    if (j === words.length) {
      result.push(i);
    }
  }
  
  return result;
}

Window Validity Criteria

  • Formed Counter: Track unique chars meeting requirement
  • Valid Window: formed === required
  • Expand: Add right char, check if formed increases
  • Shrink: Remove left char, check if formed decreases
  • Update Result: Only when window is valid and smaller
Note: Key Pattern
  • Use two maps: required frequencies and window frequencies
  • Formed tracks chars with exact frequency match
  • Expand until valid, then shrink while maintaining validity
  • O(n) time: each character visited at most twice (right + left)

4. Group Anagrams Pattern

Approach Key Generation Time Space
Sorted String Key Sort characters: "eat" → "aet" O(n * k log k) O(n * k)
Character Count Key Frequency array: [1,0,0,1,1...] for "eat" O(n * k) O(n * k)
Prime Number Hash Product of primes for each char O(n * k) O(n * k)

Example: Group Anagrams Using Sorted Key

function groupAnagrams(strs) {
  const groups = new Map();
  
  for (const str of strs) {
    // Sort string to create key
    const key = str.split('').sort().join('');
    
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(str);
  }
  
  return Array.from(groups.values());
}

console.log(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"], ["tan","nat"], ["bat"]]

// Why it works:
// "eat" → sort → "aet"
// "tea" → sort → "aet" (same key!)
// "ate" → sort → "aet" (same key!)
// All anagrams produce identical sorted string

Example: Using Character Count as Key

function groupAnagramsCharCount(strs) {
  const groups = new Map();
  
  for (const str of strs) {
    // Create frequency array as key
    const count = new Array(26).fill(0);
    
    for (const char of str) {
      count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // Convert array to string key
    const key = count.join('#');
    
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(str);
  }
  
  return Array.from(groups.values());
}

// Example with detailed trace:
// "eat" → [1,0,0,0,1,0,...,0,1] → "1#0#0#0#1#...#1"
// "tea" → [1,0,0,0,1,0,...,0,1] → "1#0#0#0#1#...#1" (same!)

// Alternative: Use object as map
function groupAnagramsObject(strs) {
  const groups = {};
  
  for (const str of strs) {
    const count = new Array(26).fill(0);
    for (const char of str) {
      count[char.charCodeAt(0) - 97]++;
    }
    const key = count.toString();
    
    if (!groups[key]) {
      groups[key] = [];
    }
    groups[key].push(str);
  }
  
  return Object.values(groups);
}
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  
  const count = new Array(26).fill(0);
  
  for (let i = 0; i < s.length; i++) {
    count[s.charCodeAt(i) - 97]++;
    count[t.charCodeAt(i) - 97]--;
  }
  
  return count.every(c => c === 0);
}

// Find all anagrams of p in s
function findAnagrams(s, p) {
  const result = [];
  const pCount = new Array(26).fill(0);
  const windowCount = new Array(26).fill(0);
  
  // Count characters in p
  for (const char of p) {
    pCount[char.charCodeAt(0) - 97]++;
  }
  
  for (let i = 0; i < s.length; i++) {
    // Add new character to window
    windowCount[s.charCodeAt(i) - 97]++;
    
    // Remove old character if window too large
    if (i >= p.length) {
      windowCount[s.charCodeAt(i - p.length) - 97]--;
    }
    
    // Check if current window is anagram
    if (i >= p.length - 1 && arraysEqual(pCount, windowCount)) {
      result.push(i - p.length + 1);
    }
  }
  
  return result;
}

function arraysEqual(arr1, arr2) {
  for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] !== arr2[i]) return false;
  }
  return true;
}

console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]

5. String Permutation in String Check

Problem Type Technique Key Insight Complexity
Check if Permutation Compare character frequencies Same frequency → permutation possible O(n)
Permutation in String Sliding window of fixed size Window matches pattern frequency O(n)
Generate All Permutations Backtracking or iterative Swap elements recursively O(n!)

Example: Check Permutation in String

function checkInclusion(s1, s2) {
  if (s1.length > s2.length) return false;
  
  const s1Count = new Array(26).fill(0);
  const windowCount = new Array(26).fill(0);
  
  // Count characters in s1
  for (const char of s1) {
    s1Count[char.charCodeAt(0) - 97]++;
  }
  
  // Sliding window
  for (let i = 0; i < s2.length; i++) {
    // Add right character
    windowCount[s2.charCodeAt(i) - 97]++;
    
    // Remove left character if window too large
    if (i >= s1.length) {
      windowCount[s2.charCodeAt(i - s1.length) - 97]--;
    }
    
    // Check if window matches s1
    if (i >= s1.length - 1 && matches(s1Count, windowCount)) {
      return true;
    }
  }
  
  return false;
}

function matches(arr1, arr2) {
  for (let i = 0; i < 26; i++) {
    if (arr1[i] !== arr2[i]) return false;
  }
  return true;
}

console.log(checkInclusion("ab", "eidbaooo")); // true ("ba" is permutation)
console.log(checkInclusion("ab", "eidboaoo")); // false

// Optimized: Use difference counter
function checkInclusionOptimized(s1, s2) {
  if (s1.length > s2.length) return false;
  
  const count = new Array(26).fill(0);
  
  // Initialize: count s1 chars as positive, first window as negative
  for (let i = 0; i < s1.length; i++) {
    count[s1.charCodeAt(i) - 97]++;
    count[s2.charCodeAt(i) - 97]--;
  }
  
  let diff = 0;
  for (const c of count) {
    if (c !== 0) diff++;
  }
  
  if (diff === 0) return true;
  
  // Slide window
  for (let i = s1.length; i < s2.length; i++) {
    const rightIdx = s2.charCodeAt(i) - 97;
    const leftIdx = s2.charCodeAt(i - s1.length) - 97;
    
    // Add right
    if (count[rightIdx] === 0) diff++;
    count[rightIdx]--;
    if (count[rightIdx] === 0) diff--;
    
    // Remove left
    if (count[leftIdx] === 0) diff++;
    count[leftIdx]++;
    if (count[leftIdx] === 0) diff--;
    
    if (diff === 0) return true;
  }
  
  return false;
}

Example: Generate All Permutations

function permute(nums) {
  const result = [];
  
  function backtrack(path, used) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      
      path.push(nums[i]);
      used[i] = true;
      
      backtrack(path, used);
      
      path.pop();
      used[i] = false;
    }
  }
  
  backtrack([], new Array(nums.length).fill(false));
  return result;
}

console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

// String permutations
function permuteString(s) {
  const result = [];
  const chars = s.split('');
  
  function swap(i, j) {
    [chars[i], chars[j]] = [chars[j], chars[i]];
  }
  
  function permute(start) {
    if (start === chars.length) {
      result.push(chars.join(''));
      return;
    }
    
    for (let i = start; i < chars.length; i++) {
      swap(start, i);
      permute(start + 1);
      swap(start, i); // backtrack
    }
  }
  
  permute(0);
  return result;
}

console.log(permuteString("abc")); 
// ["abc", "acb", "bac", "bca", "cab", "cba"]

6. Longest Repeating Character Replacement Problem

Concept Strategy Formula Complexity
Sliding Window Expand right, shrink if replacements > k windowSize - maxFreq <= k O(n)
Max Frequency Track most frequent character in window Others can be replaced to match max O(26n) = O(n)
Valid Window Window valid if replacements ≤ k len - maxCount ≤ k Check per iteration

Example: Longest Repeating Character Replacement

function characterReplacement(s, k) {
  const count = new Array(26).fill(0);
  let left = 0;
  let maxCount = 0; // Most frequent char in current window
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const rightIdx = s.charCodeAt(right) - 65; // 'A' = 65
    count[rightIdx]++;
    
    // Update max frequency in current window
    maxCount = Math.max(maxCount, count[rightIdx]);
    
    // Window size - max frequency = characters to replace
    // If more than k, shrink window
    while (right - left + 1 - maxCount > k) {
      const leftIdx = s.charCodeAt(left) - 65;
      count[leftIdx]--;
      left++;
      // Note: We don't update maxCount here (optimization)
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

console.log(characterReplacement("ABAB", 2)); // 4 (replace both B → "AAAA")
console.log(characterReplacement("AABABBA", 1)); // 4 (replace 1 B → "AABAA")

// Trace for "ABAB", k=2:
// Window "A": len=1, maxCount=1, replacements=0, valid
// Window "AB": len=2, maxCount=1, replacements=1, valid
// Window "ABA": len=3, maxCount=2, replacements=1, valid
// Window "ABAB": len=4, maxCount=2, replacements=2, valid ✓
// Result: 4 (can replace 2 B's to get "AAAA")

Example: Alternative with Explicit Max Count Update

function characterReplacementExplicit(s, k) {
  const count = {};
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;
    
    // Get current max frequency
    const maxCount = Math.max(...Object.values(count));
    
    // Shrink if invalid
    while (right - left + 1 - maxCount > k) {
      count[s[left]]--;
      if (count[s[left]] === 0) {
        delete count[s[left]];
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

// Related: Longest Substring with At Most K Distinct Characters
function lengthOfLongestSubstringKDistinct(s, k) {
  if (k === 0) return 0;
  
  const count = new Map();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) || 0) + 1);
    
    // Shrink if more than k distinct characters
    while (count.size > k) {
      count.set(s[left], count.get(s[left]) - 1);
      if (count.get(s[left]) === 0) {
        count.delete(s[left]);
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3 ("ece")
Note: Key insight: windowSize - maxFreq = characters to replace. If this exceeds k, window is invalid. We don't need to update maxCount when shrinking because we only care about finding a larger window, not maintaining exact maxCount.

Summary: String Matching Pattern

  • Longest Substring No Repeat: Sliding window with HashMap - jump left to duplicate's next position - O(n)
  • Longest Palindrome: Expand around center O(n²), or Manacher's algorithm O(n) with mirror property
  • Minimum Window Substring: Two pointers with frequency maps - expand right until valid, shrink left while valid
  • Group Anagrams: Use sorted string or character count array as key - anagrams map to same key
  • Permutation Check: Fixed-size sliding window with frequency comparison - O(n) with 26-size array
  • Character Replacement: Window valid when (size - maxFreq) ≤ k - track most frequent character
  • Frequency Tracking: Use Map/Object for flexible chars, Array[26] for lowercase letters (faster)
  • Sliding Window Template: Expand right, check validity, shrink left, update result
  • Key Insight: Most string problems use sliding window or frequency maps - choose data structure based on character set size

Related Cheat Sheets

Algorithm Patterns

Prefix Sum and Cumulative Arrays

Algorithm Patterns

Cyclic Sort Pattern

Algorithm Patterns

Monotonic Stack and Queue Patterns

Algorithm Patterns

Divide and Conquer Pattern