Strings – DSA Notes

9/3/2025

Problems on sliding window, anagrams, KMP/Rabin-Karp, parsing and more.

📌 Summary Table

Problem	Approach	Time Complexity	Space
Can Convert String in K Moves	Count needed shifts, schedule using `+26` offsets	O(n)	O(26)
Longest Substring Without Repeating Chars	Sliding window + last index map	O(n)	O(Alphabet)
Permutation in Substring	Fixed window, 26-count balance	O(n)	O(26)
Shortest Unique Prefix	Trie (or O(N²) brute force)	O(N·L²) here	O(N·L)
Implement strStr	Naive substring search	O(n·m)	O(1)
Reverse Words in String	Split + rebuild	O(n)	O(n)
Longest Palindromic Substring	Expand around centers	O(n²)	O(1)
Roman to Integer	Scan with subtraction rule	O(n)	O(1)
String to Integer (ATOI)	Parse char by char	O(n)	O(1)
Longest Common Prefix	Sort + compare first & last	O(n·logn·L)	O(1)
Repeated String Match	Append until length ≥ target	O(n·m)	O(n)
Rabin–Karp	Rolling hash substring search	O(n+m) expected	O(1)
KMP	Prefix LPS + scan	O(n+m)	O(m)
Min Chars to Prepend Palindrome	LPS on `s + $ + rev(s)`	O(n)	O(n)
Valid Anagram	Count frequencies	O(n)	O(Alphabet)
Count and Say	Recursive + run-length encode	O(n·len)	O(len)
Compare Version Numbers	Split by `.` and compare ints	O(n)	O(n)

Can Convert String in K Moves

Problem.
Given strings s and t, determine if s can be converted to t in ≤ k moves.
At move i (1-indexed), you can shift one character by i positions mod 26.

Idea.

Compute needed shift d for each char.
Each d can be reused every 26 moves.
Use a frequency map to track how many times each shift is used.

class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if (s.length() != t.length()) return false;
        HashMap<Integer, Integer> used = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int dist = (t.charAt(i) - s.charAt(i) + 26) % 26;
            if (dist == 0) continue; // Already matching
            int cnt = used.getOrDefault(dist, 0);
            int move = dist + 26 * cnt; // Schedule at dist, dist+26, dist+52, ...
            if (move > k) return false;
            used.put(dist, cnt + 1);
        }
        return true;
    }
}

Key Takeaway. Use shift frequency scheduling with +26 increments.

Longest Substring Without Repeating Characters

Problem. Find the length of the longest substring without repeating characters.

Idea.

Sliding window with last-seen index map.
Move left pointer whenever we see a duplicate.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int best = 0, left = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (last.containsKey(c)) 
                left = Math.max(left, last.get(c) + 1); // Jump left past duplicate
            last.put(c, r);
            best = Math.max(best, r - left + 1);
        }
        return best;
    }
}

Key Takeaway. Classic sliding window with hashmap.

Permutation in Substring (Check Inclusion)

Problem. Check if s1’s permutation is a substring of s2.

Idea.

Maintain count difference array of length 26.
Use sliding window of size s1.length().
If counts match (all zero), found a permutation.

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;
        int[] cnt = new int[26];
        for (int i = 0; i < n1; i++) {
            cnt[s1.charAt(i)-'a']++;
            cnt[s2.charAt(i)-'a']--;
        }
        if (allZero(cnt)) return true;
        for (int i = n1; i < n2; i++) {
            cnt[s2.charAt(i)-'a']--;
            cnt[s2.charAt(i-n1)-'a']++;
            if (allZero(cnt)) return true;
        }
        return false;
    }
    private boolean allZero(int[] a) {
        for (int x: a) if (x != 0) return false;
        return true;
    }
}

Key Takeaway. Fixed window + char count balance.

Shortest Unique Prefix for Every Word

Problem. Find the shortest unique prefix of each word in a list.

Idea.

Typically solved with Trie.
Here: brute force O(N²) prefix checking.

class Solution {
    static String[] findPrefixes(String[] arr, int N) {
        String[] out = new String[N];
        for (int i = 0; i < N; i++) {
            int len = 1;
            while (len <= arr[i].length()) {
                String pref = arr[i].substring(0, len);
                boolean unique = true;
                for (int j = 0; j < N; j++) {
                    if (i == j) continue;
                    if (arr[j].startsWith(pref)) { unique = false; break; }
                }
                if (unique) { out[i] = pref; break; }
                len++;
            }
            if (out[i] == null) out[i] = arr[i]; // fallback
        }
        return out;
    }
}

Key Takeaway. Normally use a Trie with prefix counts.

Implement strStr

Problem. Return index of first occurrence of needle in haystack.

Idea.

Naive substring search.
Optimized versions use KMP/Rabin-Karp.

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        for (int i = 0; i + needle.length() <= haystack.length(); i++) {
            int j = 0;
            while (j < needle.length() && haystack.charAt(i+j) == needle.charAt(j)) j++;
            if (j == needle.length()) return i;
        }
        return -1;
    }
}

Key Takeaway. Naive O(n·m); KMP improves to linear.

Reverse Words in a String

Problem. Reverse the order of words in a string.

class Solution {
    public String reverseWords(String s) {
        String[] w = s.trim().split("\\s+"); // Split by spaces
        StringBuilder sb = new StringBuilder();
        for (int i = w.length-1; i >= 0; i--) {
            sb.append(w[i]);
            if (i > 0) sb.append(' ');
        }
        return sb.toString();
    }
}

Key Takeaway. Split + reverse words.

Longest Palindromic Substring

Problem. Find the longest palindromic substring.

Idea.

Expand around each character (and between characters).
Track max length found.

class Solution {
    private int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        return r - l - 1; // length
    }
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expand(s, i, i);   // odd
            int len2 = expand(s, i, i+1); // even
            int len = Math.max(len1, len2);
            if (len > end - start + 1) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
}

Key Takeaway. Expand-around-center is simple O(n²).

Roman to Integer

Problem. Convert a Roman numeral to integer.

Idea.

Add value if ≥ next value.
Subtract if smaller than next.

class Solution {
    private int val(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
        }
        return 0;
    }
    public int romanToInt(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int v = val(s.charAt(i));
            if (i + 1 < s.length() && v < val(s.charAt(i+1))) res -= v;
            else res += v;
        }
        return res;
    }
}

Key Takeaway. Check next symbol for subtractive rule.

String to Integer (ATOI)

Problem. Convert string to integer with handling whitespace, sign, and overflow.

class Solution {
    public int myAtoi(String s) {
        int i = 0, n = s.length();
        while (i < n && s.charAt(i) == ' ') i++; // skip spaces
        int sign = 1;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-'))
            sign = s.charAt(i++) == '-' ? -1 : 1;
        long val = 0;
        while (i < n && Character.isDigit(s.charAt(i))) {
            val = val * 10 + (s.charAt(i++) - '0');
            long cur = sign * val;
            if (cur > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (cur < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        return (int)(sign * val);
    }
}

Key Takeaway. Careful parsing with overflow checks.

Longest Common Prefix

Problem. Find longest common prefix among strings.

Idea.

Sort array.
Compare first and last string only.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs);
        String a = strs[0], b = strs[strs.length-1];
        int i = 0, m = Math.min(a.length(), b.length());
        while (i < m && a.charAt(i) == b.charAt(i)) i++;
        return a.substring(0, i);
    }
}

Key Takeaway. Sorting trick → compare first & last.

Repeated String Match

Problem. Given a and b, repeat a until it contains b. Return min repeats or -1.

class Solution {
    private boolean isMatch(String a, String b) {
        for (int i = 0; i + b.length() <= a.length(); i++) {
            if (a.regionMatches(i, b, 0, b.length())) return true;
        }
        return false;
    }
    public int repeatedStringMatch(String a, String b) {
        String s = a;
        int ans = 1;
        while (s.length() < b.length()) { s += a; ans++; }
        if (isMatch(s, b)) return ans;
        s += a;
        return isMatch(s, b) ? ans + 1 : -1;
    }
}

Key Takeaway. Keep appending a until b fits.

Rabin–Karp

Problem. Substring search using rolling hash.

Compute hash of pattern and window.
Slide and update in O(1).

Key Takeaway. Expected linear-time substring search with rolling hash.

KMP (Knuth–Morris–Pratt)

Problem. Efficient substring search.

Idea.

Precompute LPS (longest proper prefix = suffix).
Use it to skip comparisons.

class KMP {
    private int[] lps(String p) {
        int n = p.length(), len = 0;
        int[] lps = new int[n];
        for (int i = 1; i < n; ) {
            if (p.charAt(i) == p.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return lps;
    }
    public int search(String text, String pat) {
        int[] l = lps(pat);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pat.charAt(j)) {
                i++; j++;
                if (j == pat.length()) return i - j;
            } else if (j > 0) j = l[j - 1];
            else i++;
        }
        return -1;
    }
}

Key Takeaway. Precompute prefix function to skip redundant checks.

Minimum Characters to Prepend to Make Palindrome

Problem. Find min chars to prepend to string to make it palindrome.

Idea.

Build s + $ + reverse(s).
LPS of this string gives overlap length.

class Solution {
    private int[] lps(String s) {
        int n = s.length(), len = 0;
        int[] lps = new int[n];
        for (int i = 1; i < n; ) {
            if (s.charAt(i) == s.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return lps;
    }
    public int minCharsToPrepend(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        String t = s + "$" + rev;
        int[] lp = lps(t);
        return s.length() - lp[lp.length - 1];
    }
}

Key Takeaway. Trick: use LPS on s+$+rev(s).

Valid Anagram

Problem. Check if two strings are anagrams.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i)-'a']++;
        for (int i = 0; i < t.length(); i++) 
            if (--cnt[t.charAt(i)-'a'] < 0) return false;
        return true;
    }
}

Key Takeaway. Count characters and compare.

Count and Say

Problem. Return the n-th term of the count-and-say sequence.

class Solution {
    public String countAndSay(int n) {
        if (n == 1) return "1";
        String prev = countAndSay(n - 1) + "#"; // Sentinel
        StringBuilder sb = new StringBuilder();
        int count = 1;
        for (int i = 0; i < prev.length() - 1; i++) {
            if (prev.charAt(i) == prev.charAt(i + 1)) count++;
            else { sb.append(count).append(prev.charAt(i)); count = 1; }
        }
        return sb.toString();
    }
}

Key Takeaway. Build recursively → run-length encoding.

Compare Version Numbers

Problem. Compare two version numbers given as strings.

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] a = version1.split("\\.");
        String[] b = version2.split("\\.");
        int n = Math.max(a.length, b.length);
        for (int i = 0; i < n; i++) {
            int x = i < a.length ? Integer.parseInt(a[i]) : 0;
            int y = i < b.length ? Integer.parseInt(b[i]) : 0;
            if (x < y) return -1;
            if (x > y) return 1;
        }
        return 0;
    }
}

Key Takeaway. Split by "." and compare integers component-wise.