🔑 String Patterns — PHP

Parent: Strings PHP Index

---

Pattern Overview

---

Pattern 1: Two Pointers

Two pointers on a string: left starts at 0, right at strlen-1. Move inward.

Problem 1.1 — Valid Palindrome (LC-125)

Problem: Alphanumeric only, case-insensitive palindrome check.

---

🧠 How to Approach This

Step 1 — Recognize: Skip non-alphanumeric. Compare from both ends moving inward.

Step 2: Use ctype_alnum($c) to check alphanumeric. strtolower to normalize.

function isPalindrome(string $s): bool {
    $lo = 0;
    $hi = strlen($s) - 1;
    while ($lo < $hi) {
        while ($lo < $hi && !ctype_alnum($s[$lo])) $lo++;
        while ($lo < $hi && !ctype_alnum($s[$hi])) $hi--;
        if (strtolower($s[$lo]) !== strtolower($s[$hi])) return false;
        $lo++; $hi--;
    }
    return true;
}

echo isPalindrome("A man, a plan, a canal: Panama") ? 'yes' : 'no'; // yes
echo isPalindrome("race a car") ? 'yes' : 'no';                      // no

Time: O(n) | Space: O(1)

---

Problem 1.2 — Reverse Vowels in String (LC-345)

---

🧠 How to Approach This

Step 1: Two pointers from both ends. Skip non-vowels. Swap vowels. Move inward.

function reverseVowels(string $s): string {
    $chars  = str_split($s);
    $vowels = ['a','e','i','o','u','A','E','I','O','U'];
    $lo = 0; $hi = count($chars) - 1;
    while ($lo < $hi) {
        while ($lo < $hi && !in_array($chars[$lo], $vowels)) $lo++;
        while ($lo < $hi && !in_array($chars[$hi], $vowels)) $hi--;
        if ($lo < $hi) {
            [$chars[$lo], $chars[$hi]] = [$chars[$hi], $chars[$lo]];
            $lo++; $hi--;
        }
    }
    return implode('', $chars);
}

echo reverseVowels("hello");   // "holle"
echo reverseVowels("leetcode"); // "leotcede"

Time: O(n) | Space: O(n)

---

Pattern 2: Sliding Window

Window expands right, shrinks from left when constraint violated.

Problem 2.1 — Longest Substring Without Repeating Characters (LC-3)

---

🧠 How to Approach This

Step 1 — Window: Map char → last index. When duplicate found at right: move left to map[c]+1.

Step 2 — Track max: max = max(max, right - left + 1)

function lengthOfLongestSubstring(string $s): int {
    $map   = [];
    $max   = 0;
    $left  = 0;
    for ($r = 0; $r < strlen($s); $r++) {
        $c = $s[$r];
        if (isset($map[$c]) && $map[$c] >= $left) {
            $left = $map[$c] + 1;
        }
        $map[$c] = $r;
        $max = max($max, $r - $left + 1);
    }
    return $max;
}

echo lengthOfLongestSubstring("abcabcbb"); // 3
echo lengthOfLongestSubstring("pwwkew");   // 3

Time: O(n) | Space: O(min(n,26))

---

Problem 2.2 — Minimum Window Substring (LC-76) [H]

Problem: Find minimum window in s containing all characters of t.

---

🧠 How to Approach This

Step 1 — Recognize: Sliding window + frequency map.

Step 2 — Key insight: Track have and need counts. Expand right, shrink left when all needed chars are satisfied.

function minWindow(string $s, string $t): string {
    if (strlen($t) > strlen($s)) return '';

    $need = []; foreach (str_split($t) as $c) $need[$c] = ($need[$c] ?? 0) + 1;
    $have  = []; $formed = 0; $required = count($need);
    $best  = ''; $lo = 0;

    for ($r = 0; $r < strlen($s); $r++) {
        $c = $s[$r];
        $have[$c] = ($have[$c] ?? 0) + 1;
        if (isset($need[$c]) && $have[$c] === $need[$c]) $formed++;

        while ($formed === $required) {
            $window = substr($s, $lo, $r - $lo + 1);
            if ($best === '' || strlen($window) < strlen($best)) $best = $window;

            $leftChar = $s[$lo++];
            $have[$leftChar]--;
            if (isset($need[$leftChar]) && $have[$leftChar] < $need[$leftChar]) $formed--;
        }
    }
    return $best;
}

echo minWindow("ADOBECODEBANC", "ABC"); // "BANC"

Time: O(n+m) | Space: O(n+m)

---

Pattern 3: Hashing / Frequency Count

Problem 3.1 — Valid Anagram (LC-242)

---

🧠 How to Approach This

Step 1: Count frequency of each letter in both strings. If frequencies match → anagram.

function isAnagram(string $a, string $b): bool {
    if (strlen($a) !== strlen($b)) return false;
    $freq = array_fill(0, 26, 0);
    for ($i = 0; $i < strlen($a); $i++) {
        $freq[ord($a[$i]) - ord('a')]++;
        $freq[ord($b[$i]) - ord('a')]--;
    }
    foreach ($freq as $v) if ($v !== 0) return false;
    return true;
}
echo isAnagram("anagram","nagaram") ? 'yes' : 'no'; // yes

Time: O(n) | Space: O(1)

---

Problem 3.2 — Group Anagrams (LC-49)

---

🧠 How to Approach This

Step 1 — Key insight: Anagrams have the same sorted form. Group by sorted key.

function groupAnagrams(array $strs): array {
    $groups = [];
    foreach ($strs as $s) {
        $chars = str_split($s);
        sort($chars);
        $key = implode('', $chars);
        $groups[$key][] = $s;
    }
    return array_values($groups);
}

print_r(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

Time: O(n × k log k) | Space: O(n×k)

---

Pattern 4: Expand Around Center (Palindromes)

Problem 4.1 — Longest Palindromic Substring (LC-5)

---

🧠 How to Approach This

Step 1 — Recognize: Every palindrome expands from its center.

Step 2: Expand from each index (odd) and each pair (even). Track longest expansion.

function longestPalindrome(string $s): string {
    $best = '';

    function expand(string $s, int $lo, int $hi): string {
        while ($lo >= 0 && $hi < strlen($s) && $s[$lo] === $s[$hi]) {
            $lo--; $hi++;
        }
        return substr($s, $lo + 1, $hi - $lo - 1);
    }

    for ($i = 0; $i < strlen($s); $i++) {
        $odd  = expand($s, $i, $i);         // odd length center
        $even = expand($s, $i, $i + 1);     // even length center
        if (strlen($odd)  > strlen($best)) $best = $odd;
        if (strlen($even) > strlen($best)) $best = $even;
    }
    return $best;
}

echo longestPalindrome("babad");  // "bab"
echo longestPalindrome("cbbd");   // "bb"

Time: O(n²) | Space: O(1)

---

Pattern 5: Stack

Problem 5.1 — Valid Parentheses (LC-20)

---

🧠 How to Approach This

Step 1: Push open brackets. On close bracket: pop and check match. Empty at end → valid.

function isValid(string $s): bool {
    $stack = [];
    $map   = [')'=>'(', ']'=>'[', '}'=>'{'];
    foreach (str_split($s) as $c) {
        if (in_array($c, ['(','[','{'])) { $stack[] = $c; }
        elseif (isset($map[$c])) {
            if (empty($stack) || array_pop($stack) !== $map[$c]) return false;
        }
    }
    return empty($stack);
}
echo isValid("()[]{}") ? 'yes' : 'no'; // yes
echo isValid("([)]")   ? 'yes' : 'no'; // no

Time: O(n) | Space: O(n)

---

Problem 5.2 — Decode String (LC-394)

Problem: "3[a2[c]]" → "accaccacc"

---

🧠 How to Approach This

Step 1: Use two stacks: one for counts, one for strings. On ']': pop and repeat.

function decodeString(string $s): string {
    $countStack  = [];
    $stringStack = [];
    $curr        = '';
    $k           = 0;

    foreach (str_split($s) as $c) {
        if (is_numeric($c)) {
            $k = $k * 10 + (int)$c;
        } elseif ($c === '[') {
            $countStack[]  = $k;
            $stringStack[] = $curr;
            $curr = ''; $k = 0;
        } elseif ($c === ']') {
            $times = array_pop($countStack);
            $prev  = array_pop($stringStack);
            $curr  = $prev . str_repeat($curr, $times);
        } else {
            $curr .= $c;
        }
    }
    return $curr;
}

echo decodeString("3[a]2[bc]");   // "aaabcbc"
echo decodeString("3[a2[c]]");    // "accaccacc"

Time: O(n × max_k) | Space: O(n)

---

Pattern 6: KMP — Efficient Pattern Search

Why KMP? Standard strpos is O(n×m). KMP is O(n+m).

Build LPS (Longest Prefix Suffix) Array

function buildLPS(string $pat): array {
    $m   = strlen($pat);
    $lps = array_fill(0, $m, 0);
    $len = 0; $i = 1;
    while ($i < $m) {
        if ($pat[$i] === $pat[$len]) { $lps[$i++] = ++$len; }
        elseif ($len > 0)             { $len = $lps[$len - 1]; }
        else                          { $lps[$i++] = 0; }
    }
    return $lps;
}

function kmpSearch(string $text, string $pat): int {
    $n   = strlen($text);
    $m   = strlen($pat);
    $lps = buildLPS($pat);
    $i   = 0; $j = 0;
    while ($i < $n) {
        if ($text[$i] === $pat[$j]) { $i++; $j++; }
        if ($j === $m) return $i - $j; // found
        elseif ($i < $n && $text[$i] !== $pat[$j]) {
            $j > 0 ? $j = $lps[$j - 1] : $i++;
        }
    }
    return -1;
}

echo kmpSearch("aaacaaaa", "aaaa"); // 4

Time: O(n+m) | Space: O(m)

---

Pattern Summary