Working with String Matching

1. Understanding String Matching Algorithms

Algorithm	Description	Time Complexity	Space Complexity
Brute Force	Compares every possible substring of text with pattern	`O(n*m)`	`O(1)`
KMP (Knuth-Morris-Pratt)	Uses failure function to avoid redundant comparisons	`O(n+m)`	`O(m)`
Rabin-Karp	Uses hash function to find pattern in text	`O(n+m)` average	`O(1)`
Boyer-Moore	Skips characters based on mismatched character rules	`O(n*m)` worst case, `O(n/m)` average	`O(k)` where k is alphabet size

Example: KMP Algorithm Implementation

function buildFailureFunction(pattern) {
  const failure = new Array(pattern.length).fill(0);
  let j = 0;

  for (let i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = failure[j - 1];
    }

    if (pattern[i] === pattern[j]) {
      j++;
    }

    failure[i] = j;
  }

  return failure;
}

function kmpSearch(text, pattern) {
  const failure = buildFailureFunction(pattern);
  let j = 0;

  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = failure[j - 1];
    }

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

    if (j === pattern.length) {
      return i - pattern.length + 1;
    }
  }

  return -1;
}

Note: The KMP algorithm is particularly useful when the pattern has overlapping subpatterns, allowing it to skip unnecessary comparisons.

2. Validating Palindromes

Property	Description	Example
isPalindrome	Checks if a string is a palindrome	`"racecar"`
isPalindromeIgnoreCase	Checks if a string is a palindrome, ignoring case	`"RaceCar"`
isPalindromeWithSpaces	Checks if a string is a palindrome, ignoring spaces and punctuation	`"A man, a plan, a canal: Panama"`

Example: Basic Palindrome Check

function isPalindrome(str) {
  const cleanStr = str.toLowerCase();
  return cleanStr === cleanStr.split('').reverse().join('');
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

Example: Case-Insensitive Palindrome Check

function isPalindromeIgnoreCase(str) {
  const cleanStr = str.toLowerCase();
  return cleanStr === cleanStr.split('').reverse().join('');
}

console.log(isPalindromeIgnoreCase("RaceCar")); // true
console.log(isPalindromeIgnoreCase("Madam"));   // true

Example: Palindrome with Spaces and Punctuation

function isPalindromeWithSpaces(str) {
  const cleanStr = str.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
  return cleanStr === cleanStr.split('').reverse().join('');
}

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

Note: The time complexity of basic palindrome checking is O(n), where n is the length of the string. Space complexity is also O(n) due to creating a reversed copy.

3. Checking for Anagrams

Method	Description	Time Complexity	Space Complexity
Sorting Approach	Sort characters of both strings and compare.	`O(n log n)`	`O(n)`
Character Frequency Count	Count character frequencies in both strings and compare.	`O(n)`	`O(k)` where `k` is the number of unique characters
Built-in Functions (JavaScript)	Use `sort()` and `join()` to compare sorted strings.	`O(n log n)`	`O(n)`

Example: Sorting Approach

function areAnagrams(str1, str2) {
  // Normalize strings (lowercase, remove spaces)
  const cleanStr1 = str1.toLowerCase().replace(/\s/g, '');
  const cleanStr2 = str2.toLowerCase().replace(/\s/g, '');

  // Sort characters and compare
  const sorted1 = cleanStr1.split('').sort().join('');
  const sorted2 = cleanStr2.split('').sort().join('');

  return sorted1 === sorted2;
}

// Example usage
console.log(areAnagrams("listen", "silent")); // true
console.log(areAnagrams("hello", "bello"));   // false

Example: Character Frequency Count

function areAnagrams(str1, str2) {
  // Normalize strings (lowercase, remove spaces)
  const cleanStr1 = str1.toLowerCase().replace(/\s/g, '');
  const cleanStr2 = str2.toLowerCase().replace(/\s/g, '');

  // Early exit if lengths differ
  if (cleanStr1.length !== cleanStr2.length) return false;

  // Count character frequencies
  const freqMap = {};
  for (let char of cleanStr1) {
    freqMap[char] = (freqMap[char] || 0) + 1;
  }

  // Subtract frequencies from second string
  for (let char of cleanStr2) {
    if (!freqMap[char]) return false;
    freqMap[char]--;
  }

  // Ensure all counts are zero
  return Object.values(freqMap).every(count => count === 0);
}

// Example usage
console.log(areAnagrams("anagram", "nagaram")); // true
console.log(areAnagrams("rat", "car"));         // false

Note: Anagrams must have the same length and same character frequencies, but not necessarily the same order.

4. Grouping Anagrams Together

An anagram is a word or phrase formed by rearranging the letters of another, using all the original letters exactly once. Grouping anagrams together is a common problem in string matching and algorithm design.

Approach	Description	Time Complexity	Space Complexity
Sorting	Sort characters of each string and use the sorted string as a key in a hash map.	`O(n * m log m)`	`O(n * m)`
Character Counting	Count character frequencies for each string and use the count as a key in a hash map.	`O(n * m)`	`O(n * m)`

Example: Using Sorting to Group Anagrams

function groupAnagrams(strs) {
  const map = new Map();
  for (const str of strs) {
    const sortedStr = str.split('').sort().join('');
    if (!map.has(sortedStr)) {
      map.set(sortedStr, []);
    }
    map.get(sortedStr).push(str);
  }
  return Array.from(map.values());
}

// Example usage
const input = [&#34;eat&#34;, &#34;tea&#34;, &#34;tan&#34;, &#34;ate&#34;, &#34;nat&#34;, &#34;bat&#34;];
console.log(groupAnagrams(input));
// Output: [[&#34;eat&#34;, &#34;tea&#34;, &#34;ate&#34;], [&#34;tan&#34;, &#34;nat&#34;], [&#34;bat&#34;]]

Example: Using Character Counting to Group Anagrams

function getCharCount(str) {
  const count = new Array(26).fill(0);
  for (const char of str) {
    count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
  return count.join(',');
}

function groupAnagrams(strs) {
  const map = new Map();
  for (const str of strs) {
    const key = getCharCount(str);
    if (!map.has(key)) {
      map.set(key, []);
    }
    map.get(key).push(str);
  }
  return Array.from(map.values());
}

// Example usage
const input = [&#34;eat&#34;, &#34;tea&#34;, &#34;tan&#34;, &#34;ate&#34;, &#34;nat&#34;, &#34;bat&#34;];
console.log(groupAnagrams(input));
// Output: [[&#34;eat&#34;, &#34;tea&#34;, &#34;ate&#34;], [&#34;tan&#34;, &#34;nat&#34;], [&#34;bat&#34;]]

Note: The character counting approach assumes all strings consist of lowercase letters only. For a more general solution, sorting or using a map to count character frequencies is preferred.

5. Implementing String Compression

Method	Description	Time Complexity	Space Complexity
Run-Length Encoding (RLE)	Encodes consecutive repeated characters with count and character	`O(n)`	`O(n)`
LZ77 (Lempel-Ziv 1977)	Uses sliding window to find repeated sequences	`O(n^2)` worst case	`O(n)`
LZ78 (Lempel-Ziv 1978)	Builds dictionary of phrases dynamically	`O(n)`	`O(d)` where `d` is dictionary size

Example: Run-Length Encoding Implementation

function runLengthEncode(str) {
  if (!str) return "";

  let result = "";
  let count = 1;
  let currentChar = str[0];

  for (let i = 1; i <= str.length; i++) {
    if (str[i] === currentChar) {
      count++;
    } else {
      result += currentChar + count;
      currentChar = str[i];
      count = 1;
    }
  }

  return result;
}

// Example usage:
console.log(runLengthEncode("aaabbc")); // "a3b2c1"

Example: LZ77 Compression

function lz77Compress(text, windowSize = 10) {
  const output = [];
  let i = 0;

  while (i < text.length) {
    let matchLength = 0;
    let matchOffset = 0;

    // Find longest match in sliding window
    for (let j = Math.max(0, i - windowSize); j < i; j++) {
      let len = 0;
      while (i + len < text.length && 
             text[j + len] === text[i + len]) {
        len++;
      }
      if (len > matchLength) {
        matchLength = len;
        matchOffset = i - j;
      }
    }

    if (matchLength > 0) {
      output.push([matchOffset, matchLength, text[i + matchLength]]);
      i += matchLength + 1;
    } else {
      output.push([0, 0, text[i]]);
      i++;
    }
  }

  return output;
}

// Example usage:
console.log(lz77Compress("ababab")); // [[0,0,"a"], [2,3,"b"]]

Note: Run-Length Encoding is most effective for strings with long sequences of repeated characters. LZ77 and LZ78 are more suitable for general-purpose compression.

6. Finding Longest Palindromic Substring

Approach	Description	Time Complexity	Space Complexity
Expand Around Centers	For each possible center (both odd and even length palindromes), expand outward while characters match.	`O(n²)`	`O(1)`
Manacher's Algorithm	Preprocesses string to handle even-length palindromes uniformly and uses previously computed values for optimization.	`O(n)`	`O(n)`

Example: Expand Around Centers

function longestPalindrome(s) {
  let start = 0;
  let maxLen = 1;

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

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i); // Odd-length
    expandAroundCenter(i, i + 1); // Even-length
  }

  return s.substring(start, start + maxLen);
}

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

Example: Manacher's Algorithm

function manachers(s) {
  // Preprocess string to handle even-length palindromes
  let processed = '#' + s.split('').join('#') + '#';
  let P = new Array(processed.length).fill(0);
  let center = 0;
  let right = 0;

  for (let i = 0; i < processed.length; i++) {
    let mirror = 2 * center - i;

    if (i < right) {
      P[i] = Math.min(right - i, P[mirror]);
    }

    try {
      while (processed[i + P[i] + 1] === processed[i - P[i] - 1]) {
        P[i]++;
      }
    } catch (e) {}

    if (i + P[i] > right) {
      center = i;
      right = i + P[i];
    }
  }

  let maxLen = Math.max(...P);
  let centerIndex = P.indexOf(maxLen);
  let start = (centerIndex - maxLen) / 2;
  return s.substring(start, start + maxLen);
}

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

Note: Manacher's algorithm is optimal for finding the longest palindromic substring in linear time, but it requires preprocessing and is more complex to understand than the expand-around-centers approach.

7. Finding Longest Palindromic Subsequence

Property	Description	Example
Problem	Finds the longest subsequence that is a palindrome in a given string.	`Input: "bbbab"` → `Output: 4`
Approach	Dynamic Programming (DP) - Build a 2D table to store lengths of palindromic subsequences.
Time Complexity	O(n²)
Space Complexity	O(n²)

Example: Implementation using Dynamic Programming

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

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

    // Fill the table for substrings of length 2 to n
    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];
}

// Example usage
console.log(longestPalindromeSubseq("bbbab")); // Output: 4

Note: The longest palindromic subsequence is not necessarily a substring. It's a sequence of characters that maintains relative order but does not need to be contiguous.

8. Implementing KMP Algorithm

Component	Description	Details
Pattern	String to search for	`"ABABCABAA"`
Text	String to search in	`"ABABDABACDABABCABAA"`
LPS Array	Longest Proper Prefix which is also Suffix	`[0, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1]`

Example: KMP Algorithm Implementation in JavaScript

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

  while (i < pattern.length) {
    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 lps = buildLPSArray(pattern);
  let i = 0;
  let j = 0;

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

    if (j === pattern.length) {
      console.log("Pattern found at index " + (i - j));
      j = lps[j - 1];
    } else if (i < text.length && pattern[j] !== text[i]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
}

// Example usage:
const text = "ABABDABACDABABCABAA";
const pattern = "ABABCABAA";
KMPSearch(text, pattern);

Note: The KMP algorithm preprocesses the pattern to build an LPS (Longest Proper Prefix which is also Suffix) array, enabling efficient pattern matching without backtracking in the text.

9. Implementing Rabin-Karp Algorithm

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find any one of a set of pattern strings in a text. It is particularly useful when searching for multiple patterns simultaneously.

Feature	Description	Details
Time Complexity	Average Case	O(n + m) where n is the length of text and m is the length of pattern
Space Complexity	Space Required	O(1) for basic implementation
Hash Function	Used for Pattern Matching	Rolling hash function to compute hash values efficiently

Example: Basic Implementation of Rabin-Karp

function rabinKarp(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  const d = 256; // Number of characters in the alphabet
  const q = 101; // A prime number for modulo operation

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

  let p = 0, t = 0;
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  for (let i = 0; i <= n - m; i++) {
    if (p === t) {
      let j;
      for (j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) break;
      }
      if (j === m) {
        return i; // Pattern found at index i
      }
    }

    if (i < n - m) {
      t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
      if (t < 0) t += q;
    }
  }

  return -1; // Pattern not found
}

// Example usage:
const text = "ABABCABABA";
const pattern = "ABABA";
console.log(rabinKarp(text, pattern)); // Output: 5

Note: The Rabin-Karp algorithm uses a rolling hash to efficiently compute the hash of each substring. It is efficient for multiple pattern searches but can have worst-case performance O(nm) if hash collisions occur frequently.

10. Finding Longest Repeating Substring

Approach	Description	Time Complexity	Space Complexity
Brute Force	Check all possible substrings for repetition using nested loops.	`O(n^3)`	`O(1)`
Suffix Array	Build a suffix array and find the longest common prefix (LCP) between adjacent suffixes.	`O(n log n)`	`O(n)`
Rolling Hash (Rabin-Karp)	Use hash functions to detect repeated substrings efficiently with sliding window.	`O(n^2)` average	`O(n)`

Example: Brute Force Approach

function longestRepeatingSubstring(s) {
  let result = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j < s.length; j++) {
      let substr = s.substring(i, j);
      if (s.indexOf(substr, j) !== -1 && substr.length > result.length) {
        result = substr;
      }
    }
  }
  return result;
}

console.log(longestRepeatingSubstring("banana")); // "ana"

Example: Rolling Hash Approach

function longestRepeatingSubstring(s) {
  let n = s.length;
  let left = 1, right = n - 1;
  let result = '';

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let hashSet = new Set();
    let hash = 0;
    let base = 256;
    let power = 1;

    for (let i = 0; i < mid; i++) {
      power = (power * base) % 1000000007;
    }

    for (let i = 0; i < mid; i++) {
      hash = (hash * base + s.charCodeAt(i)) % 1000000007;
    }

    hashSet.add(hash);

    let found = false;
    for (let i = mid; i < n; i++) {
      hash = (hash * base - s.charCodeAt(i - mid) * power + s.charCodeAt(i)) % 1000000007;
      if (hashSet.has(hash)) {
        found = true;
        result = s.substring(i - mid + 1, i + 1);
        break;
      }
      hashSet.add(hash);
    }

    if (found) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

console.log(longestRepeatingSubstring("abcdefabc")); // "abc"

Note: The rolling hash approach uses binary search over the length of the substring and a hash set to efficiently check for repeating patterns.

11. Finding Distinct Subsequences

Property	Description	Example
distinctSubsequences	Counts the number of distinct subsequences of string T in string S	`distinctSubsequences("rabbbit", "rabbit") = 3`

Example: Counting Distinct Subsequences

function distinctSubsequences(s, t) {
    const m = s.length;
    const n = t.length;
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    
    return dp[m][n];
}

// Example usage:
console.log(distinctSubsequences("rabbbit", "rabbit")); // Output: 3

Note: The algorithm uses dynamic programming where dp[i][j] represents the number of distinct subsequences of the first j characters of t in the first i characters of s.

12. Implementing Trie for Prefix Matching

Example: Basic Trie Implementation

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

// Usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.startsWith("app")); // true

Method	Description	Time Complexity	Space Complexity
insert(word)	Inserts a word into the trie	O(m)	O(m × N)
search(word)	Checks if a word exists in the trie	O(m)	O(1)
startsWith(prefix)	Checks if any word starts with the given prefix	O(m)	O(1)

Note: m is the length of the word/prefix, and N is the size of the alphabet.

Key Features of Trie

Efficient prefix matching
Fast insertion and search operations
Memory efficient for large datasets with common prefixes