String Algorithms - Complete Guide | Chinese Powered Labs

String algorithms are fundamental for text processing, pattern matching, and manipulation. This guide covers essential string algorithms and common problems.

String Basics #

Character Operations #

const str = 'Hello';

// Character access
console.log(str[0]);           // 'H'
console.log(str.charAt(0));    // 'H'
console.log(str.charCodeAt(0)); // 72

// String is immutable
str[0] = 'h';  // No effect
console.log(str);  // 'Hello'

// Convert to array for manipulation
const arr = str.split('');
arr[0] = 'h';
console.log(arr.join(''));  // 'hello'

String Comparison #

function compareStrings(s1, s2) {
  if (s1 === s2) return 0;
  return s1 < s2 ? -1 : 1;
}

console.log(compareStrings('abc', 'abd'));  // -1
console.log(compareStrings('abc', 'abc'));  // 0
console.log(compareStrings('abd', 'abc'));  // 1

Pattern Matching #

Naive Pattern Matching #

function naiveSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const positions = [];

  for (let i = 0; i <= n - m; i++) {
    let j;
    for (j = 0; j < m; j++) {
      if (text[i + j] !== pattern[j]) {
        break;
      }
    }
    if (j === m) {
      positions.push(i);
    }
  }

  return positions;
}

console.log(naiveSearch('ababcabcab', 'abc'));
// [2, 5]

KMP Algorithm #

Knuth-Morris-Pratt for efficient pattern matching.

function computeLPS(pattern) {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let len = 0;
  let i = 1;

  while (i < m) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

function kmpSearch(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const lps = computeLPS(pattern);
  const positions = [];

  let i = 0;  // text index
  let j = 0;  // pattern index

  while (i < n) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }

    if (j === m) {
      positions.push(i - j);
      j = lps[j - 1];
    } else if (i < n && text[i] !== pattern[j]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return positions;
}

console.log(kmpSearch('ababcabcab', 'abc'));
// [2, 5]

Rabin-Karp Algorithm #

Rolling hash for pattern matching.

function rabinKarp(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const d = 256;  // Number of characters
  const q = 101;  // Prime number
  const positions = [];

  let p = 0;  // Pattern hash
  let t = 0;  // Text hash
  let h = 1;

  // h = d^(m-1) % q
  for (let i = 0; i < m - 1; i++) {
    h = (h * d) % q;
  }

  // Calculate initial hash values
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  // Slide pattern over text
  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      // Hash match - verify actual characters
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) {
        positions.push(i);
      }
    }

    // Calculate hash for next window
    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) {
        t += q;
      }
    }
  }

  return positions;
}

console.log(rabinKarp('ababcabcab', 'abc'));
// [2, 5]

Substring Problems #

Longest Substring Without Repeating Characters #

function lengthOfLongestSubstring(s) {
  const seen = new Map();
  let maxLen = 0;
  let start = 0;

  for (let end = 0; end < s.length; end++) {
    const char = s[end];

    if (seen.has(char) && seen.get(char) >= start) {
      start = seen.get(char) + 1;
    }

    seen.set(char, end);
    maxLen = Math.max(maxLen, end - start + 1);
  }

  return maxLen;
}

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

Longest Palindromic Substring #

function longestPalindrome(s) {
  if (s.length < 2) return s;

  let start = 0;
  let maxLen = 0;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1;
  }

  for (let i = 0; i < s.length; i++) {
    // Odd length palindrome
    const len1 = expandAroundCenter(i, i);
    // Even length palindrome
    const len2 = expandAroundCenter(i, i + 1);

    const len = Math.max(len1, len2);

    if (len > maxLen) {
      maxLen = len;
      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'

Minimum Window Substring #

function minWindow(s, t) {
  const need = new Map();
  const window = new Map();

  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }

  let left = 0;
  let right = 0;
  let valid = 0;
  let start = 0;
  let len = Infinity;

  while (right < s.length) {
    const char = s[right];
    right++;

    if (need.has(char)) {
      window.set(char, (window.get(char) || 0) + 1);
      if (window.get(char) === need.get(char)) {
        valid++;
      }
    }

    while (valid === need.size) {
      if (right - left < len) {
        start = left;
        len = right - left;
      }

      const leftChar = s[left];
      left++;

      if (need.has(leftChar)) {
        if (window.get(leftChar) === need.get(leftChar)) {
          valid--;
        }
        window.set(leftChar, window.get(leftChar) - 1);
      }
    }
  }

  return len === Infinity ? '' : s.substring(start, start + len);
}

console.log(minWindow('ADOBECODEBANC', 'ABC'));  // 'BANC'

Anagram Problems #

Valid Anagram #

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const count = new Map();

  for (const char of s) {
    count.set(char, (count.get(char) || 0) + 1);
  }

  for (const char of t) {
    if (!count.has(char)) return false;
    count.set(char, count.get(char) - 1);
    if (count.get(char) < 0) return false;
  }

  return true;
}

console.log(isAnagram('anagram', 'nagaram'));  // true
console.log(isAnagram('rat', 'car'));          // false

Group Anagrams #

function groupAnagrams(strs) {
  const map = new Map();

  for (const str of strs) {
    const key = str.split('').sort().join('');

    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(str);
  }

  return Array.from(map.values());
}

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

String Transformation #

Longest Common Subsequence #

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

console.log(longestCommonSubsequence('abcde', 'ace'));  // 3 ('ace')

Edit Distance #

function minDistance(word1, word2) {
  const m = word1.length;
  const n = word2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  // Initialize first row and column
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1,     // Delete
          dp[i][j - 1] + 1,     // Insert
          dp[i - 1][j - 1] + 1  // Replace
        );
      }
    }
  }

  return dp[m][n];
}

console.log(minDistance('horse', 'ros'));  // 3
console.log(minDistance('intention', 'execution'));  // 5

Interleaving String #

function isInterleave(s1, s2, s3) {
  const m = s1.length;
  const n = s2.length;

  if (m + n !== s3.length) return false;

  const dp = Array(m + 1).fill(false).map(() => Array(n + 1).fill(false));
  dp[0][0] = true;

  // First column
  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  }

  // First row
  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
                 (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }

  return dp[m][n];
}

console.log(isInterleave('aabcc', 'dbbca', 'aadbbcbcac'));  // true

String Reversal #

Reverse String #

function reverseString(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }

  return s;
}

const arr = ['h', 'e', 'l', 'l', 'o'];
reverseString(arr);
console.log(arr);  // ['o', 'l', 'l', 'e', 'h']

Reverse Words #

function reverseWords(s) {
  return s.trim()
    .split(/\s+/)
    .reverse()
    .join(' ');
}

console.log(reverseWords('  hello   world  '));  // 'world hello'

Reverse Words III #

Reverse each word individually.

function reverseWordsIII(s) {
  return s.split(' ')
    .map(word => word.split('').reverse().join(''))
    .join(' ');
}

console.log(reverseWordsIII("Let's take LeetCode contest"));
// "s'teL ekat edoCteeL tsetnoc"

String Encoding #

Encode and Decode Strings #

class Codec {
  encode(strs) {
    return strs.map(s => `${s.length}#${s}`).join('');
  }

  decode(s) {
    const result = [];
    let i = 0;

    while (i < s.length) {
      // Find the delimiter
      let j = i;
      while (s[j] !== '#') j++;

      const length = parseInt(s.substring(i, j));
      const str = s.substring(j + 1, j + 1 + length);
      result.push(str);

      i = j + 1 + length;
    }

    return result;
  }
}

const codec = new Codec();
const encoded = codec.encode(['hello', 'world']);
console.log(encoded);  // '5#hello5#world'
console.log(codec.decode(encoded));  // ['hello', 'world']

String Compression #

function compress(chars) {
  let write = 0;
  let read = 0;

  while (read < chars.length) {
    const char = chars[read];
    let count = 0;

    while (read < chars.length && chars[read] === char) {
      read++;
      count++;
    }

    chars[write++] = char;

    if (count > 1) {
      for (const digit of String(count)) {
        chars[write++] = digit;
      }
    }
  }

  return write;
}

const chars = ['a', 'a', 'b', 'b', 'c', 'c', 'c'];
const len = compress(chars);
console.log(chars.slice(0, len));  // ['a', '2', 'b', '2', 'c', '3']

Palindrome Problems #

Valid Palindrome #

function isPalindrome(s) {
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');

  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

console.log(isPalindrome('A man, a plan, a canal: Panama'));  // true
console.log(isPalindrome('race a car'));  // false

Longest Palindromic Subsequence #

function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array(n).fill(0).map(() => Array(n).fill(0));

  // Every single character is a palindrome
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[0][n - 1];
}

console.log(longestPalindromeSubseq('bbbab'));  // 4 ('bbbb')

Time Complexity #

Algorithm	Time Complexity	Space Complexity
Naive Search	O(n*m)	O(1)
KMP	O(n + m)	O(m)
Rabin-Karp	O(n + m) avg, O(n*m) worst	O(1)
Longest Substring	O(n)	O(min(n, k))
LCS	O(n*m)	O(n*m)
Edit Distance	O(n*m)	O(n*m)

n = text length, m = pattern length, k = character set size

Best Practices #

Use appropriate algorithm - KMP for pattern matching, sliding window for substrings
Consider character set - ASCII vs Unicode affects space
Hash for anagrams - Sorted string or character count
Two pointers - Efficient for palindromes and reversal
Dynamic programming - LCS, edit distance need DP
Sliding window - Substring problems often use this
Handle edge cases - Empty strings, single characters
Space optimization - DP can often use O(n) instead of O(n²)

String algorithms are essential for text processing. Master these patterns to solve a wide range of string problems efficiently.