🔑 String Patterns — JavaScript

Parent: Strings JS Index

---

Pattern Overview

---

Pattern 1: Two Pointers

Problem 1.1 — Valid Palindrome (LC-125)

---

🧠 How to Approach This

Step 1 — Recognize: Skip non-alphanumeric. Compare from both ends. Case-insensitive.

Step 2: Use /[a-z0-9]/i.test(c) to check alphanumeric. toLowerCase() to normalize.

function isPalindrome(s) {
    let lo = 0, hi = s.length - 1;
    while (lo < hi) {
        while (lo < hi && !/[a-z0-9]/i.test(s[lo])) lo++;
        while (lo < hi && !/[a-z0-9]/i.test(s[hi])) hi--;
        if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
        lo++; hi--;
    }
    return true;
}

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

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

---

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

---

🧠 How to Approach This

Step 1: Two pointers on char array. Skip non-vowels. Swap vowels. Move inward.

function reverseVowels(s) {
    const chars  = s.split('');
    const vowels = new Set('aeiouAEIOU');
    let lo = 0, hi = chars.length - 1;
    while (lo < hi) {
        while (lo < hi && !vowels.has(chars[lo])) lo++;
        while (lo < hi && !vowels.has(chars[hi])) hi--;
        if (lo < hi) { [chars[lo], chars[hi]] = [chars[hi], chars[lo]]; lo++; hi--; }
    }
    return chars.join('');
}

console.log(reverseVowels("hello"));    // "holle"
console.log(reverseVowels("leetcode")); // "leotcede"

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

---

Pattern 2: Sliding Window

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

---

🧠 How to Approach This

Step 1 — Map + Window: Map char → last seen index. When duplicate: move left to map.get(c)+1.

function lengthOfLongestSubstring(s) {
    const map = new Map();
    let max = 0, left = 0;
    for (let r = 0; r < s.length; r++) {
        if (map.has(s[r]) && map.get(s[r]) >= left) left = map.get(s[r]) + 1;
        map.set(s[r], r);
        max = Math.max(max, r - left + 1);
    }
    return max;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3
console.log(lengthOfLongestSubstring("pwwkew"));   // 3

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

---

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

---

🧠 How to Approach This

Step 1 — Two Maps: need from t, have for window. Track formed count (how many chars satisfied).

Step 2: Expand right always. Shrink left while all chars satisfied. Track minimum window.

function minWindow(s, t) {
    if (t.length > s.length) return '';
    const need = new Map();
    for (const c of t) need.set(c, (need.get(c) || 0) + 1);

    const have = new Map();
    let formed = 0, required = need.size;
    let best = '', lo = 0;

    for (let r = 0; r < s.length; r++) {
        const c = s[r];
        have.set(c, (have.get(c) || 0) + 1);
        if (need.has(c) && have.get(c) === need.get(c)) formed++;

        while (formed === required) {
            const win = s.slice(lo, r + 1);
            if (!best || win.length < best.length) best = win;
            const lc = s[lo++];
            have.set(lc, have.get(lc) - 1);
            if (need.has(lc) && have.get(lc) < need.get(lc)) formed--;
        }
    }
    return best;
}

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

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

---

Pattern 3: Hashing / Frequency Count

Problem 3.1 — Valid Anagram (LC-242)

function isAnagram(a, b) {
    if (a.length !== b.length) return false;
    const freq = new Array(26).fill(0);
    for (let i = 0; i < a.length; i++) {
        freq[a.charCodeAt(i) - 97]++;
        freq[b.charCodeAt(i) - 97]--;
    }
    return freq.every(v => v === 0);
}
console.log(isAnagram("anagram","nagaram")); // true

---

Problem 3.2 — Group Anagrams (LC-49)

---

🧠 How to Approach This

Step 1 — Key: Sort each string → identical for anagrams. Use as Map key.

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

console.log(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

Problem 4.1 — Longest Palindromic Substring (LC-5)

---

🧠 How to Approach This

Step 1 — Insight: Every palindrome expands from its center. Try each center (2n-1 centers total).

Step 2: Expand function returns longest palindrome centered at (lo, hi).

function longestPalindrome(s) {
    let best = '';

    function expand(lo, hi) {
        while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
        return s.slice(lo + 1, hi);
    }

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

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

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

---

Pattern 5: Stack

Problem 5.1 — Valid Parentheses (LC-20)

function isValid(s) {
    const stack = [];
    const map = {')':'(', ']':'[', '}':'{'};
    for (const c of s) {
        if ('([{'.includes(c)) { stack.push(c); }
        else if (map[c]) {
            if (!stack.length || stack.pop() !== map[c]) return false;
        }
    }
    return stack.length === 0;
}
console.log(isValid("()[]{}"));  // true
console.log(isValid("([)]"));    // false

---

Problem 5.2 — Decode String (LC-394)

---

🧠 How to Approach This

Step 1 — Two stacks: One for counts, one for strings. On '[': push both. On ']': pop and repeat.

function decodeString(s) {
    const countStack  = [];
    const stringStack = [];
    let curr = '', k = 0;

    for (const c of s) {
        if (c >= '0' && c <= '9') {
            k = k * 10 + parseInt(c);
        } else if (c === '[') {
            countStack.push(k);
            stringStack.push(curr);
            curr = ''; k = 0;
        } else if (c === ']') {
            const times = countStack.pop();
            curr = stringStack.pop() + curr.repeat(times);
        } else {
            curr += c;
        }
    }
    return curr;
}

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

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

---

Pattern 6: KMP Pattern Matching

function buildLPS(pat) {
    const m = pat.length, lps = new Array(m).fill(0);
    let len = 0, i = 1;
    while (i < m) {
        if (pat[i] === pat[len]) { lps[i++] = ++len; }
        else if (len > 0)         { len = lps[len - 1]; }
        else                      { lps[i++] = 0; }
    }
    return lps;
}

function kmpSearch(text, pat) {
    const n = text.length, m = pat.length;
    const lps = buildLPS(pat);
    let i = 0, j = 0;
    while (i < n) {
        if (text[i] === pat[j]) { i++; j++; }
        if (j === m) return i - j;
        else if (i < n && text[i] !== pat[j]) {
            j > 0 ? (j = lps[j - 1]) : i++;
        }
    }
    return -1;
}

console.log(kmpSearch("aaacaaaa", "aaaa")); // 4

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

---

Pattern Summary