Implementing String Algorithms

1. Implementing KMP Algorithm

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

Example: KMP Search Implementation

function KMPSearch(pattern, text) {
    const lps = computeLPSArray(pattern);
    let i = 0; // index for text
    let j = 0; // index for pattern

    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++;
            }
        }
    }
}

function computeLPSArray(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;
}

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

Note: The KMP algorithm avoids unnecessary character comparisons by using the information from previous matches.

Key Features of KMP Algorithm

Time Complexity: O(n + m)
Space Complexity: O(m)
Preprocessing of pattern to build LPS array
Efficient for large texts and patterns

2. Implementing Rabin-Karp

Feature	Description	Implementation
Pattern	Substring to search for in text	`"abc"`
Text	String to search in	`"abcdefabc"`
Hash Function	Used to compute hash values for substrings	`hash = (d * prev_hash + text[i] - text[i - pattern_length] * d^(pattern_length - 1)) % q`
Base (d)	Number of characters in the alphabet	`256`
Modulus (q)	Prime number to avoid overflow	`101`

Example: Rabin-Karp Implementation in JavaScript

function rabinKarp(text, pattern) {
  const d = 256;
  const q = 101;
  const m = pattern.length;
  const n = text.length;

  let p = 0; // hash value for pattern
  let t = 0; // hash value for text
  let h = 1;

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

  // Calculate hash value of pattern and first window of text
  for (let i = 0; i < m; i++) {
    p = (d * p + pattern.charCodeAt(i)) % q;
    t = (d * t + text.charCodeAt(i)) % q;
  }

  // Slide the pattern over text one by one
  for (let i = 0; i <= n - m; i++) {
    // Check if hash values match
    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
      }
    }

    // Calculate hash value for next window of text
    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 = "abcdefabc";
const pattern = "abc";
console.log(rabinKarp(text, pattern)); // Output: 0

Note: The Rabin-Karp algorithm uses a rolling hash to find all occurrences of a pattern in a text. It is efficient for multiple pattern searches but can have worst-case time complexity of O(nm) when many spurious hits occur.

3. Implementing Z-Algorithm

The Z-algorithm is a linear-time string searching algorithm that computes the length of the longest substring starting at each position which matches a prefix of the string.

Property	Description	Example
Z-array	Array where Z[i] represents the length of the longest substring starting at index i that matches a prefix of the string.	`[0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0]`

Example: Z-Algorithm Implementation

function zAlgorithm(str) {
  const n = str.length;
  const z = new Array(n).fill(0);
  let l = 0, r = 0;

  for (let i = 1; i < n; i++) {
    if (i <= r) {
      z[i] = Math.min(r - i + 1, z[i - l]);
    }

    while (i + z[i] < n && str[z[i]] === str[i + z[i]]) {
      z[i]++;
    }

    if (i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }

  return z;
}

console.log(zAlgorithm("abcabcabc")); // [0, 0, 0, 3, 0, 0, 3, 0, 0, 3, 0]

Note: The Z-algorithm is useful for pattern matching and string compression. It runs in O(n) time.

4. Finding Longest Palindromic Substring

Algorithm	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 and uses previously computed values to avoid redundant checks	`O(n)`	`O(n)`

Example: Expand Around Centers

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

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

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

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

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

Example: Manacher's Algorithm

function manachers(s) {
  // Preprocess the 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.

5. Checking Anagrams

Method	Description	Time Complexity	Space Complexity
Sorting Approach	Sort characters of both strings and compare.	`O(n log n)`	`O(n)`
Character Count	Count character frequencies in both strings and compare.	`O(n)`	`O(k)` where `k` is unique characters

Example: Character Count Approach

function areAnagrams(str1, str2) {
  if (str1.length !== str2.length) return false;

  const charCount = {};

  for (let char of str1) {
    charCount[char] = (charCount[char] || 0) + 1;
  }

  for (let char of str2) {
    if (!charCount[char]) return false;
    charCount[char]--;
  }

  return true;
}

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

Note: Case-sensitive comparison. For case-insensitive, convert strings to lowercase before processing.

6. Finding All Anagrams

Method	Description	Time Complexity	Space Complexity
Sorting Approach	Sort characters of each string and compare sorted strings.	`O(n * m log m)`	`O(m)`
Character Frequency Count	Count character frequencies for each string and compare frequency maps.	`O(n * m)`	`O(1)` (fixed size for 26 lowercase letters)

Example: Character Frequency Count

function findAnagrams(s, p) {
    const result = [];
    const pCount = new Array(26).fill(0);
    const windowCount = new Array(26).fill(0);

    // Count characters in pattern p
    for (let char of p) {
        pCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

    const windowSize = p.length;

    // Sliding window over string s
    for (let i = 0; i < s.length; i++) {
        // Add current character to window count
        windowCount[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;

        // Remove character that is out of window
        if (i >= windowSize) {
            windowCount[s.charCodeAt(i - windowSize) - 'a'.charCodeAt(0)]--;
        }

        // Compare counts when window is full
        if (i >= windowSize - 1 && JSON.stringify(pCount) === JSON.stringify(windowCount)) {
            result.push(i - windowSize + 1);
        }
    }

    return result;
}

// Example usage:
const s = "cbaebabacd";
const p = "abc";
console.log(findAnagrams(s, p)); // [0, 6]

Note: The character frequency approach is more efficient for large inputs as it avoids sorting and uses fixed-size arrays for counting.

7. Implementing String Compression

Algorithm	Description	Time Complexity	Space Complexity
Run-Length Encoding (RLE)	Encodes consecutive repeated characters with count and character	`O(n)`	`O(n)`
Lempel-Ziv-Welch (LZW)	Variable-length prefix coding; builds dictionary dynamically	`O(n)`	`O(2^k)` where `k` is the dictionary size
Huffman Coding	Variable-length encoding based on character frequency	`O(n log n)`	`O(n)`

Example: Run-Length Encoding

function runLengthEncode(str) {
  if (str.length === 0) return "";
  let result = "";
  let count = 1;
  let currentChar = str[0];

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

  return result;
}

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

Example: LZW Compression

function lzwCompress(input) {
  const dict = new Map();
  const output = [];
  let code = 256;

  // Initialize dictionary with single characters
  for (let i = 0; i < 256; i++) {
    dict.set(String.fromCharCode(i), i);
  }

  let current = "";
  for (let i = 0; i < input.length; i++) {
    const char = input[i];
    const combined = current + char;

    if (dict.has(combined)) {
      current = combined;
    } else {
      output.push(dict.get(current));
      dict.set(combined, code++);
      current = char;
    }
  }

  if (current) output.push(dict.get(current));
  return output;
}

// Example usage:
console.log(lzwCompress("ABABABA")); // [65, 66, 65, 66, 65]

Note: LZW is a lossless compression algorithm commonly used in GIF and TIFF formats.

Warning: Huffman coding is optimal for fixed input, but requires prior knowledge of character frequencies.

8. Counting Distinct Subsequences

Given two strings s and t, the task is to count the number of distinct subsequences of s that equal t.

Parameter	Description	Example
s	Source string to find subsequences in	`"rabbbit"`
t	Target subsequence to count	`"rabbit"`

Example: Counting Subsequences

function numDistinct(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++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[m][n];
}

console.log(numDistinct("rabbbit", "rabbit")); // Output: 3

Note: The dynamic programming approach uses a 2D array where dp[i][j] represents the number of distinct subsequences of the first i characters of s that match the first j characters of t.

Algorithm Summary

Use dynamic programming with a 2D array dp[i][j]
dp[0][0] = 1 (empty string matches empty pattern once)
If s[i-1] === t[j-1], then dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
Else dp[i][j] = dp[i-1][j]
Return dp[m][n] for final count

9. Implementing Wildcard Matching

Pattern	Description	Examples	Match Result
?	Matches any single character	`"a?b"`, `"abc"`	`true` for `"aab"`, `false` for `"ab"`
*	Matches any sequence of characters (including empty)	`"a*b"`, `"ab"`	`true` for `"axxb"`, `"ab"`
?	Matches any single character	`"a?b"`, `"abc"`	`true` for `"aab"`, `false` for `"ab"`
*	Matches any sequence of characters (including empty)	`"a*b"`, `"ab"`	`true` for `"axxb"`, `"ab"`

Example: Basic Wildcard Matching Implementation

function isMatch(s, p) {
  const dp = Array(s.length + 1).fill().map(() => Array(p.length + 1).fill(false));
  dp[0][0] = true;

  for (let j = 1; j <= p.length; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = dp[0][j - 1];
    }
  }

  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      if (p[j - 1] === '*') {
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }

  return dp[s.length][p.length];
}

// Example usage:
console.log(isMatch("aab", "c*a*b")); // false
console.log(isMatch("adceb", "*a*b*")); // true

Note: The wildcard matching algorithm uses dynamic programming to efficiently match strings with ? (any single character) and * (any sequence of characters).

Key Concepts

Wildcard Characters: ? matches any single character, * matches any sequence including empty.
Dynamic Programming: The solution uses a 2D boolean array to store intermediate matching results.
Time Complexity: O(m*n) where m is the length of string and n is the length of pattern.

10. Implementing Regex Matching

Feature	Description	Implementation
Basic Pattern Matching	Matches literal strings or characters	`function match(pattern, text) { return new RegExp(pattern).test(text); }`
Anchors	`^` matches start, `$` matches end	`/^hello/.test("hello world"); // true /world$/.test("hello world"); // true`
Character Classes	Matches any one character from a set	`/[abc]/.test("a"); // true /[^abc]/.test("d"); // true`
Quantifiers	Specify repetition: `*`, `+`, `?`	`/a*/.test("aaa"); // true /a+/.test("aaa"); // true /a?/.test("a"); // true`
Groups and Captures	Group patterns with parentheses	`const match = /(\w+)@(\w+)/.exec("user@example.com"); match[1]; // "user" match[2]; // "example"`

Example: Basic Regex Engine

function simpleRegex(pattern, text) {
  const regex = new RegExp(pattern);
  return regex.test(text);
}

// Example usage:
console.log(simpleRegex("hello", "say hello world")); // true
console.log(simpleRegex("world$", "say hello world")); // true

Note: For performance-critical applications, consider using compiled regex objects or optimized engines like re2.

Warning: Regex can be vulnerable to ReDoS attacks if not carefully designed.

11. Finding Minimum Window Substring

Property	Description	Example
Input	Two strings: `s` (source string) and `t` (target string)	`s = "ADOBECODEBANC"`, `t = "ABC"`
Output	Minimum substring in `s` that contains all characters of `t`	`"BANC"`
Time Complexity	O(n)	Using sliding window technique

Example: Sliding Window Implementation

function minWindow(s, t) {
    const need = new Map();
    const window = new Map();
    for (let c of t) {
        need.set(c, (need.get(c) || 0) + 1);
    }

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

    while (right < s.length) {
        let c = s[right];
        right++;

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

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

            let d = s[left];
            left++;

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

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

// Example usage:
const s = "ADOBECODEBANC";
const t = "ABC";
console.log(minWindow(s, t)); // Output: "BANC"

Note: The sliding window technique ensures linear time complexity by maintaining a dynamic window that expands and contracts based on character inclusion.

12. Comparing String Algorithms

String Algorithm Comparison

Brute Force: Simple but inefficient for large texts; O(nm) time complexity.
KMP: Efficient for pattern matching; O(n + m) time complexity.
Boyer-Moore: Fast for large alphabets; O(nm) worst case, but often faster in practice.
Robin-Karp: Good for multiple pattern searches; O(n + m) average case, uses hashing.

Algorithm	Time Complexity (Best)	Space Complexity	Use Case
Brute Force	`O(nm)`	`O(1)`	Simple pattern matching, small inputs
KMP	`O(n + m)`	`O(m)`	Pattern matching with overlapping patterns
Boyer-Moore	`O(nm)` worst case, `O(n/m)` average	`O(m + \|Σ\|)`	Large alphabets, large texts
Robin-Karp	`O(n + m)` average	`O(1)`	Multiple pattern search, hash-based matching

Note: The Boyer-Moore algorithm is particularly effective when the alphabet size is large and the pattern length is significant.