Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

String Revision
DSA

String Revision

Quickly revise essential string operations, techniques, and common coding interview patterns.

left = 0
Initialize freq map
max_length = 0

For right in 0 to n-1:
    add s[right] to map

    While window invalid:
        remove s[left] from map
        left++

    update max_length

When to use

  • Longest substring without repeating chars
  • Minimum window substring
  • Contiguous substring constraints

Time: O(n)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (map.containsKey(c)) {
            left = Math.max(left, map.get(c) + 1);
        }

        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

2 Two Pointers (Palindrome / Reverse)

left = 0
right = n-1

While left < right:
    If s[left] != s[right]:
        return false
    left++
    right--

Return true

When to use

  • Palindrome check
  • Reverse substring
  • Compare ends
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        if (s.charAt(left) != s.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}

3 Trie (Prefix Tree)

Insert(word):
    node = root
    For each char:
        If char not in children:
            create node
        move to child
    mark end

Search(word):
    traverse chars
    return node.isEnd

When to use

  • Autocomplete
  • Prefix search
  • Dictionary matching

Time: O(length)

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

class Trie {

    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null)
                return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }
}

4 Hashing (Anagrams / Frequency)

Initialize count[26]

For char in s1:
    increment count

For char in s2:
    decrement count

If all zeros:
    anagram

When to use

  • Anagram check
  • Frequency count
  • Character mapping

Time: O(n)

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] count = new int[26];

    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }

    for (int c : count)
        if (c != 0) return false;

    return true;
}

5 KMP (Prefix Function / LPS)

Build LPS array

i = 0, j = 0

While i < text length:
    If text[i] == pattern[j]:
        i++, j++
    If j == pattern length:
        found match
    Else if mismatch:
        If j != 0:
            j = lps[j-1]
        Else:
            i++

Time: O(n + m)

public int strStr(String text, String pattern) {
    int[] lps = buildLPS(pattern);
    int i = 0, j = 0;

    while (i < text.length()) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++; j++;
            if (j == pattern.length())
                return i - j;
        } else if (j > 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }
    return -1;
}

6 Z Algorithm (Bonus)

Create Z array

Maintain window [L, R]

For i from 1 to n-1:
    If i <= R:
        Z[i] = min(R-i+1, Z[i-L])

    Expand match from i
    Update L, R if expanded

Time: O(n)

public int[] computeZ(String s) {
    int n = s.length();
    int[] z = new int[n];
    int L = 0, R = 0;

    for (int i = 1; i < n; i++) {

        if (i <= R)
            z[i] = Math.min(R - i + 1, z[i - L]);

        while (i + z[i] < n &&
               s.charAt(z[i]) == s.charAt(i + z[i]))
            z[i]++;

        if (i + z[i] - 1 > R) {
            L = i;
            R = i + z[i] - 1;
        }
    }
    return z;
}

7 Rolling Hash (Rabin–Karp Core)

Compute hash of pattern
Compute rolling hash of first window

For each next window:
    Remove left char
    Add right char
    Compare hash

Time: O(n)

public int rabinKarp(String text, String pattern) {
    int base = 256;
    int mod = 101;

    int m = pattern.length();
    int n = text.length();

    int pHash = 0, tHash = 0, power = 1;

    for (int i = 0; i < m - 1; i++)
        power = (power * base) % mod;

    for (int i = 0; i < m; i++) {
        pHash = (pHash * base + pattern.charAt(i)) % mod;
        tHash = (tHash * base + text.charAt(i)) % mod;
    }

    for (int i = 0; i <= n - m; i++) {

        if (pHash == tHash &&
            text.substring(i, i + m).equals(pattern))
            return i;

        if (i < n - m) {
            tHash = (tHash - text.charAt(i) * power) % mod;
            if (tHash < 0) tHash += mod;
            tHash = (tHash * base +
                     text.charAt(i + m)) % mod;
        }
    }
    return -1;
}

8 DP on Strings (LCS Example)

dp[m+1][n+1]

For i from 1..m:
    For j from 1..n:
        If chars match:
            dp[i][j] = 1 + dp[i-1][j-1]
        Else:
            dp[i][j] =
              max(dp[i-1][j], dp[i][j-1])

Time: O(m × n)

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {

            if (s1.charAt(i - 1) ==
                s2.charAt(j - 1))
                dp[i][j] =
                    1 + dp[i - 1][j - 1];
            else
                dp[i][j] =
                    Math.max(dp[i - 1][j],
                             dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

9 Sliding Window + Hashing (Distinct Chars)

left = 0
freq map

For right:
    add char
    While condition violated:
        remove char at left
        left++

Used for

  • At most K distinct chars
  • Exactly K distinct chars
public int lengthAtMostKDistinct(String s, int k) {
    Map<Character, Integer> map = new HashMap<>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.length(); right++) {
        map.put(s.charAt(right),
                map.getOrDefault(
                    s.charAt(right), 0) + 1);

        while (map.size() > k) {
            char leftChar = s.charAt(left);
            map.put(leftChar,
                    map.get(leftChar) - 1);
            if (map.get(leftChar) == 0)
                map.remove(leftChar);
            left++;
        }

        maxLen = Math.max(maxLen,
                          right - left + 1);
    }
    return maxLen;
}

Bitmask for Characters (Lowercase Letters)

mask = 0

For each char:
    bit = char - 'a'
    If mask & (1 << bit) != 0:
        duplicate found
    mask |= (1 << bit)

When to use

  • Unique character constraint
  • Small alphabet optimization

Time: O(n)

public boolean hasUniqueChars(String s) {
    int mask = 0;

    for (char c : s.toCharArray()) {
        int bit = c - 'a';

        if ((mask & (1 << bit)) != 0)
            return false;

        mask |= (1 << bit);
    }
    return true;
}

My Private Notes

Notes are auto-saved locally to this device.