50 String Coding Problems for Interviews — Solutions Explained

50 essential string interview problems from easy to hard — step-by-step approach, JavaScript solution, and function calls with output comments.

Jul 4, 202641 min read

Introduction

String problems are interview staples — palindromes, sliding windows, KMP, and dynamic programming on subsequences. This post covers 50 curated problems with:

Step-by-step approach
Full JavaScript implementation
Function calls with side output comments

Prerequisites: Big O notation · Hash Maps

Quick index

#	Problem	Level	Time
1	Palindrome Check	Easy	O(n)
2	Reverse a String	Easy	O(n)
3	Reverse Words	Easy	O(n)
4	Check for Rotation	Easy	O(n)
5	First Non Repeating	Easy	O(n)
6	Roman to Integer	Easy	O(n)
7	Implement Atoi	Easy	O(n)
8	Encrypt the String II	Easy	O(n)
9	Equal Point in Brackets	Easy	O(n)
10	Anagram Checking	Easy	O(n)
11	Pangram Checking	Easy	O(n)
12	Validate IP Address	Easy	O(n)
13	Add Binary Strings	Easy	O(n)
14	Integer to Words	Medium	O(log n)
15	Fizz Buzz	Medium	O(n)
16	Palindromic Sentence Check	Medium	O(n)
17	Isomorphic Strings	Medium	O(n)
18	Check for k-anagram	Medium	O(n)
19	Sort String of 0s 1s and 2s	Medium	O(n)
20	Find and Replace in String	Medium	O(n + m)
21	Look and Say Pattern	Medium	O(n · m)
22	Minimum Repetitions to Make Substring	Medium	O(n + m)
23	Excel Sheet Column Title	Medium	O(log n)
24	Find N-th Character in Pattern String	Medium	O(n · m)
25	Next Palindromic Number with Same Digits	Medium	O(n)
26	Longest Prefix Suffix	Medium	O(n)
27	Longest K Unique Characters Substring	Medium	O(n)
28	Smallest Window Containing All Characters	Medium	O(n)
29	Longest Substring Without Repeating Characters	Medium	O(n)
30	Substrings Length K with K-1 Distinct	Medium	O(n)
31	Count Number of Substrings	Medium	O(n)
32	Check Interleaved Strings	Medium	O(n · m)
33	Group Anagrams Together	Medium	O(n · k log k)
34	Rank Lexicographic Permutation	Medium	O(n²)
35	Special Keyboard	Medium	O(n · m)
36	Sum of Two Large Numbers	Medium	O(n)
37	Repeatedly Remove Adjacent Duplicates	Hard	O(n)
38	Multiply Two Strings	Hard	O(n · m)
39	Search Pattern KMP	Hard	O(n + m)
40	Search Pattern Rabin-Karp	Hard	O(n + m) avg
41	Shortest Common Supersequence Length	Hard	O(n · m)
42	Longest Substring to Form Palindrome	Hard	O(n²)
43	Longest Valid Parentheses	Hard	O(n)
44	Longest Palindromic Subsequence Length	Hard	O(n²)
45	Count Distinct Palindromic Substrings	Hard	O(n²)
46	Palindrome Substring Queries	Hard	O(n² + q)
47	Number of Distinct Subsequences	Hard	O(n · m)
48	Minimum Deletions for Palindrome	Hard	O(n²)
49	Minimum Insertions for Palindrome	Hard	O(n²)
50	Max Non-Overlapping Odd Palindrome Sum	Hard	O(n²)

Easy (1–13)

1. Palindrome Check

Difficulty: Easy · Time: O(n) · Space: O(1)

Return true if the string reads the same forward and backward (ignore case and non-alphanumeric).

Approach (step by step):

Normalize with two pointers at both ends.
Skip non-alphanumeric; compare lowercase letters.
Return false on mismatch, true when pointers cross.

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

Function calls with output

// ── Demo calls — output shown on the right ──
isPalindrome('A man, a plan, a canal: Panama') // → true
isPalindrome('race a car') // → false
isPalindrome('aba') // → true

Back to index

2. Reverse a String

Difficulty: Easy · Time: O(n) · Space: O(n)

Return a new string with characters in reverse order.

Approach (step by step):

Split into array, reverse, join — or two-pointer swap in array form.

function reverseString(s) {
  return s.split('').reverse().join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
reverseString('hello') // → "olleh"
reverseString('abc') // → "cba"

Back to index

3. Reverse Words

Difficulty: Easy · Time: O(n) · Space: O(n)

Reverse the order of words in a sentence; words separated by spaces.

Approach (step by step):

Trim, split on whitespace, reverse array, join with single space.

function reverseWords(s) {
  return s.trim().split(/\s+/).reverse().join(' ')
}

Function calls with output

// ── Demo calls — output shown on the right ──
reverseWords('the sky is blue') // → "blue is sky the"
reverseWords('  hello world  ') // → "world hello"

Back to index

4. Check for Rotation

Difficulty: Easy · Time: O(n) · Space: O(n)

Return true if s2 is a rotation of s1 (same length).

Approach (step by step):

Concatenate s1 + s1; check if it contains s2.

function isRotation(s1, s2) {
  if (s1.length !== s2.length) return false
  return (s1 + s1).includes(s2)
}

Function calls with output

// ── Demo calls — output shown on the right ──
isRotation('abcde', 'cdeab') // → true
isRotation('abcde', 'abced') // → false

Back to index

5. First Non Repeating

Difficulty: Easy · Time: O(n) · Space: O(1)

Return the first character that appears exactly once, or empty string if none.

Approach (step by step):

Count frequencies in a map, scan again for count === 1.

function firstNonRepeating(s) {
  const freq = new Map()
  for (const c of s) freq.set(c, (freq.get(c) ?? 0) + 1)
  for (const c of s) if (freq.get(c) === 1) return c
  return ''
}

Function calls with output

// ── Demo calls — output shown on the right ──
firstNonRepeating('swiss') // → "w"
firstNonRepeating('aabb') // → ""

Back to index

6. Roman to Integer

Difficulty: Easy · Time: O(n) · Space: O(1)

Convert a valid Roman numeral string to an integer.

Approach (step by step):

Map symbols to values; subtract when current value is less than next.

function romanToInt(s) {
  const map = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 }
  let total = 0
  for (let i = 0; i < s.length; i++) {
    const cur = map[s[i]],
      next = map[s[i + 1]] ?? 0
    total += cur < next ? -cur : cur
  }
  return total
}

Function calls with output

// ── Demo calls — output shown on the right ──
romanToInt('III') // → 3
romanToInt('MCMXCIV') // → 1994
romanToInt('LVIII') // → 58

Back to index

7. Implement Atoi

Difficulty: Easy · Time: O(n) · Space: O(1)

Parse string to 32-bit signed integer; stop at first non-digit; clamp overflow.

Approach (step by step):

Skip whitespace, read sign, accumulate digits with overflow check.

function myAtoi(s) {
  let i = 0
  while (i < s.length && s[i] === ' ') i++
  let sign = 1
  if (s[i] === '+' || s[i] === '-') {
    sign = s[i] === '-' ? -1 : 1
    i++
  }
  let num = 0
  while (i < s.length && s[i] >= '0' && s[i] <= '9') {
    num = num * 10 + (s[i].charCodeAt(0) - 48)
    i++
  }
  num *= sign
  const INT_MAX = 2 ** 31 - 1,
    INT_MIN = -(2 ** 31)
  if (num > INT_MAX) return INT_MAX
  if (num < INT_MIN) return INT_MIN
  return num
}

Function calls with output

// ── Demo calls — output shown on the right ──
myAtoi('42') // → 42
myAtoi('   -42') // → -42
myAtoi('4193 with words') // → 4193

Back to index

8. Encrypt the String II

Difficulty: Easy · Time: O(n) · Space: O(n)

Shift each alphabetic character forward by key positions (mod 26); preserve case.

Approach (step by step):

For each letter, shift within a-z or A-Z range using modulo wrap.

function encryptString(s, key) {
  key = ((key % 26) + 26) % 26
  return [...s]
    .map((c) => {
      if (c >= 'a' && c <= 'z') return String.fromCharCode(((c.charCodeAt(0) - 97 + key) % 26) + 97)
      if (c >= 'A' && c <= 'Z') return String.fromCharCode(((c.charCodeAt(0) - 65 + key) % 26) + 65)
      return c
    })
    .join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
encryptString('abc', 1) // → "bcd"
encryptString('xyz', 3) // → "abc"
encryptString('Hello!', 2) // → "Jgnnq!"

Back to index

9. Equal Point in Brackets

Difficulty: Easy · Time: O(n) · Space: O(1)

Find index where prefix sum of ( minus ) equals suffix balance (or -1).

Approach (step by step):

Compute total balance; scan prefix — when prefix equals half of total, return index.

function equalPoint(s) {
  let total = 0
  for (const c of s) total += c === '(' ? 1 : -1
  if (total % 2 !== 0) return -1
  const half = total / 2
  let pref = 0
  for (let i = 0; i < s.length; i++) {
    pref += s[i] === '(' ? 1 : -1
    if (pref === half) return i
  }
  return -1
}

Function calls with output

// ── Demo calls — output shown on the right ──
equalPoint('(()())') // → 2
equalPoint('())(') // → -1

Back to index

10. Anagram Checking

Difficulty: Easy · Time: O(n) · Space: O(1)

Return true if two strings are anagrams of each other.

Approach (step by step):

Sort both strings and compare, or count character frequencies.

function isAnagram(s, t) {
  if (s.length !== t.length) return false
  const cnt = Array(26).fill(0)
  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - 97]++
    cnt[t.charCodeAt(i) - 97]--
  }
  return cnt.every((x) => x === 0)
}

Function calls with output

// ── Demo calls — output shown on the right ──
isAnagram('listen', 'silent') // → true
isAnagram('rat', 'car') // → false

Back to index

11. Pangram Checking

Difficulty: Easy · Time: O(n) · Space: O(1)

Return true if the string contains every letter a-z at least once.

Approach (step by step):

Track seen letters in a Set; pangram if size is 26.

function isPangram(s) {
  const seen = new Set()
  for (const c of s.toLowerCase()) if (c >= 'a' && c <= 'z') seen.add(c)
  return seen.size === 26
}

Function calls with output

// ── Demo calls — output shown on the right ──
isPangram('The quick brown fox jumps over the lazy dog') // → true
isPangram('hello world') // → false

Back to index

12. Validate IP Address

Difficulty: Easy · Time: O(n) · Space: O(1)

Return "IPv4", "IPv6", or "Neither" for the given query string.

Approach (step by step):

Split by . or : and validate each segment per protocol rules.

function validIPAddress(queryIP) {
  const ipv4 = queryIP.split('.')
  if (ipv4.length === 4) {
    for (const p of ipv4) {
      if (!/^(0|[1-9]\d{0,2})$/.test(p) || +p > 255) return 'Neither'
    }
    return 'IPv4'
  }
  const ipv6 = queryIP.split(':')
  if (ipv6.length === 8) {
    for (const p of ipv6) {
      if (!/^[0-9a-fA-F]{1,4}$/.test(p)) return 'Neither'
    }
    return 'IPv6'
  }
  return 'Neither'
}

Function calls with output

// ── Demo calls — output shown on the right ──
validIPAddress('172.16.254.1') // → "IPv4"
validIPAddress('2001:0db8:85a3:0000:0000:8a2e:0370:7334') // → "IPv6"
validIPAddress('256.256.256.256') // → "Neither"

Back to index

13. Add Binary Strings

Difficulty: Easy · Time: O(n) · Space: O(n)

Return sum of two binary strings as a binary string.

Approach (step by step):

Add from right with carry; prepend each result bit.

function addBinary(a, b) {
  let i = a.length - 1,
    j = b.length - 1,
    carry = 0,
    out = ''
  while (i >= 0 || j >= 0 || carry) {
    const sum = (+a[i--] || 0) + (+b[j--] || 0) + carry
    out = (sum % 2) + out
    carry = Math.floor(sum / 2)
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
addBinary('11', '1') // → "100"
addBinary('1010', '1011') // → "10101"

Back to index

Medium (14–36)

14. Integer to Words

Difficulty: Medium · Time: O(log n) · Space: O(1)

Convert non-negative integer up to billions into English words.

Approach (step by step):

Chunk by thousands (billions, millions, thousands); helper for 0–999.

function numberToWords(num) {
  if (num === 0) return 'Zero'
  const ones = [
    '',
    'One',
    'Two',
    'Three',
    'Four',
    'Five',
    'Six',
    'Seven',
    'Eight',
    'Nine',
    'Ten',
    'Eleven',
    'Twelve',
    'Thirteen',
    'Fourteen',
    'Fifteen',
    'Sixteen',
    'Seventeen',
    'Eighteen',
    'Nineteen',
  ]
  const tens = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
  const chunk = (n) => {
    let s = ''
    if (n >= 100) {
      s += ones[Math.floor(n / 100)] + ' Hundred'
      n %= 100
      if (n) s += ' '
    }
    if (n >= 20) {
      s += tens[Math.floor(n / 10)]
      n %= 10
      if (n) s += ' ' + ones[n]
    } else if (n > 0) s += ones[n]
    return s.trim()
  }
  const parts = []
  const scales = ['Billion', 'Million', 'Thousand', '']
  let div = 1e9
  for (const scale of scales) {
    const v = Math.floor(num / div)
    if (v) parts.push(chunk(v) + (scale ? ' ' + scale : ''))
    num %= div
    div = Math.floor(div / 1000)
  }
  return parts.join(' ').trim()
}

Function calls with output

// ── Demo calls — output shown on the right ──
numberToWords(123) // → "One Hundred Twenty Three"
numberToWords(1000000) // → "One Million"
numberToWords(0) // → "Zero"

Back to index

15. Fizz Buzz

Difficulty: Medium · Time: O(n) · Space: O(n)

Return array of strings 1..n with Fizz/Buzz/FizzBuzz replacements.

Approach (step by step):

For each i: divisible by 15 → FizzBuzz, 3 → Fizz, 5 → Buzz, else string of i.

function fizzBuzz(n) {
  const out = []
  for (let i = 1; i <= n; i++) {
    if (i % 15 === 0) out.push('FizzBuzz')
    else if (i % 3 === 0) out.push('Fizz')
    else if (i % 5 === 0) out.push('Buzz')
    else out.push(String(i))
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
fizzBuzz(5) // → ["1","2","Fizz","4","Buzz"]
fizzBuzz(15) // → [..., "FizzBuzz"]

Back to index

16. Palindromic Sentence Check

Difficulty: Medium · Time: O(n) · Space: O(1)

Return true if sentence is a palindrome ignoring spaces and punctuation.

Approach (step by step):

Two pointers; compare alphanumeric chars case-insensitively.

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

Function calls with output

// ── Demo calls — output shown on the right ──
isPalindromeSentence('A man a plan a canal Panama') // → true
isPalindromeSentence('hello') // → false

Back to index

17. Isomorphic Strings

Difficulty: Medium · Time: O(n) · Space: O(1)

Return true if characters in s can map one-to-one to characters in t.

Approach (step by step):

Track maps s→t and t→s; reject on conflict.

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false
  const mapST = new Map(),
    mapTS = new Map()
  for (let i = 0; i < s.length; i++) {
    const a = s[i],
      b = t[i]
    if (mapST.has(a) && mapST.get(a) !== b) return false
    if (mapTS.has(b) && mapTS.get(b) !== a) return false
    mapST.set(a, b)
    mapTS.set(b, a)
  }
  return true
}

Function calls with output

// ── Demo calls — output shown on the right ──
isIsomorphic('egg', 'add') // → true
isIsomorphic('foo', 'bar') // → false

Back to index

18. Check for k-anagram

Difficulty: Medium · Time: O(n) · Space: O(1)

Return true if two strings can become anagrams by changing at most k characters.

Approach (step by step):

Count frequency differences; sum of absolute diffs / 2 must be ≤ k.

function isKAnagram(s, t, k) {
  if (s.length !== t.length) return false
  const cnt = Array(26).fill(0)
  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - 97]++
    cnt[t.charCodeAt(i) - 97]--
  }
  let diff = 0
  for (const x of cnt) diff += Math.abs(x)
  return diff / 2 <= k
}

Function calls with output

// ── Demo calls — output shown on the right ──
isKAnagram('anagram', 'grammar', 2) // → true
isKAnagram('abc', 'xyz', 2) // → false

Back to index

19. Sort String of 0s 1s and 2s

Difficulty: Medium · Time: O(n) · Space: O(1)

Sort a string of digits 0, 1, 2 in-place using Dutch national flag.

Approach (step by step):

Three pointers: low, mid, high; swap 0 to front, 2 to back.

function sort012(s) {
  const arr = s.split('')
  let lo = 0,
    mid = 0,
    hi = arr.length - 1
  while (mid <= hi) {
    if (arr[mid] === '0') {
      ;[arr[lo], arr[mid]] = [arr[mid], arr[lo]]
      lo++
      mid++
    } else if (arr[mid] === '1') mid++
    else {
      ;[arr[mid], arr[hi]] = [arr[hi], arr[mid]]
      hi--
    }
  }
  return arr.join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
sort012('201001') // → "001122"
sort012('012210') // → "001122"

Back to index

20. Find and Replace in String

Difficulty: Medium · Time: O(n + m) · Space: O(n)

Replace each occurrence of old with new in string s.

Approach (step by step):

Use split/join or scan with indexOf loop.

function findAndReplace(s, old, rep) {
  if (!old) return s
  return s.split(old).join(rep)
}

Function calls with output

// ── Demo calls — output shown on the right ──
findAndReplace('hello world', 'world', 'there') // → "hello there"
findAndReplace('aaaa', 'aa', 'b') // → "ba"

Back to index

21. Look and Say Pattern

Difficulty: Medium · Time: O(n · m) · Space: O(n)

Generate the n-th term of the look-and-say sequence starting from "1".

Approach (step by step):

Repeatedly read run-length encoding of previous term.

function lookAndSay(n) {
  let s = '1'
  for (let k = 1; k < n; k++) {
    let next = '',
      i = 0
    while (i < s.length) {
      let j = i
      while (j < s.length && s[j] === s[i]) j++
      next += j - i + s[i]
      i = j
    }
    s = next
  }
  return s
}

Function calls with output

// ── Demo calls — output shown on the right ──
lookAndSay(1) // → "1"
lookAndSay(4) // → "1211"
lookAndSay(5) // → "111221"

Back to index

22. Minimum Repetitions to Make Substring

Difficulty: Medium · Time: O(n + m) · Space: O(n + m)

Minimum times to repeat a so that b is a substring (or -1).

Approach (step by step):

Repeat a up to len(b)/len(a)+2 times; check includes; use KMP optional.

function minRepeats(a, b) {
  if (!b.length) return 0
  if (!a.length) return -1
  const rep = a.repeat(Math.ceil(b.length / a.length) + 1)
  const idx = rep.indexOf(b)
  if (idx === -1) return -1
  return Math.ceil((idx + b.length) / a.length)
}

Function calls with output

// ── Demo calls — output shown on the right ──
minRepeats('abcd', 'cdabcdab') // → 3
minRepeats('a', 'aa') // → 2

Back to index

23. Excel Sheet Column Title

Difficulty: Medium · Time: O(log n) · Space: O(log n)

Convert column number to Excel title (1 → A, 26 → Z, 27 → AA).

Approach (step by step):

Repeatedly take (n-1) mod 26 and prepend letter; n = floor((n-1)/26).

function convertToTitle(n) {
  let out = ''
  while (n > 0) {
    n--
    out = String.fromCharCode(65 + (n % 26)) + out
    n = Math.floor(n / 26)
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
convertToTitle(1) // → "A"
convertToTitle(28) // → "AB"
convertToTitle(701) // → "ZY"

Back to index

24. Find N-th Character in Pattern String

Difficulty: Medium · Time: O(n · m) · Space: O(n · m)

Pattern: each step doubles string by appending mirrored copy with first char incremented. Return n-th char (1-indexed).

Approach (step by step):

Build pattern until length ≥ n; return char at index n-1.

function nthCharPattern(n) {
  let s = 'a'
  while (s.length < n) {
    const mirror = s
      .split('')
      .reverse()
      .map((c, i) => (i === 0 ? String.fromCharCode(c.charCodeAt(0) + 1) : c))
      .join('')
    s += mirror
  }
  return s[n - 1]
}

Function calls with output

// ── Demo calls — output shown on the right ──
nthCharPattern(5) // → "b"
nthCharPattern(8) // → "a"

Back to index

25. Next Palindromic Number with Same Digits

Difficulty: Medium · Time: O(n) · Space: O(n)

Given palindrome digit string, return next smallest palindrome with same digit multiset.

Approach (step by step):

Increment left half like next permutation; mirror to right half.

function nextPalindromeSameDigits(digits) {
  const arr = digits.split('')
  const n = arr.length
  const half = Math.floor(n / 2)
  let carry = 1
  for (let i = half - 1; i >= 0 && carry; i--) {
    const sum = +arr[i] + carry
    arr[i] = String(sum % 10)
    carry = Math.floor(sum / 10)
  }
  if (carry) {
    return '1' + '0'.repeat(n - 1) + '1'
  }
  for (let i = half; i < n; i++) arr[i] = arr[n - 1 - i]
  return arr.join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
nextPalindromeSameDigits('1221') // → "2112"
nextPalindromeSameDigits('999') // → "1001"

Back to index

26. Longest Prefix Suffix

Difficulty: Medium · Time: O(n) · Space: O(n)

Return length of longest proper prefix which is also suffix (LPS / KMP failure array last value).

Approach (step by step):

Build LPS array: if chars match extend, else fall back to lps[j-1].

function lpsLength(s) {
  const lps = Array(s.length).fill(0)
  let len = 0,
    i = 1
  while (i < s.length) {
    if (s[i] === s[len]) {
      len++
      lps[i] = len
      i++
    } else if (len) len = lps[len - 1]
    else {
      lps[i] = 0
      i++
    }
  }
  return lps[s.length - 1]
}

Function calls with output

// ── Demo calls — output shown on the right ──
lpsLength('abab') // → 2
lpsLength('aaaa') // → 3
lpsLength('abc') // → 0

Back to index

27. Longest K Unique Characters Substring

Difficulty: Medium · Time: O(n) · Space: O(k)

Length of longest substring with at most k distinct characters.

Approach (step by step):

Sliding window with frequency map; shrink while distinct > k.

function longestKUnique(s, k) {
  if (k === 0) return 0
  const freq = new Map()
  let left = 0,
    best = 0
  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) ?? 0) + 1)
    while (freq.size > k) {
      const c = s[left++]
      const f = freq.get(c) - 1
      if (f === 0) freq.delete(c)
      else freq.set(c, f)
    }
    best = Math.max(best, right - left + 1)
  }
  return best
}

Function calls with output

// ── Demo calls — output shown on the right ──
longestKUnique('eceba', 2) // → 3
longestKUnique('aa', 1) // → 2

Back to index

28. Smallest Window Containing All Characters

Difficulty: Medium · Time: O(n) · Space: O(1)

Minimum window in s containing all characters of t (including duplicates).

Approach (step by step):

Expand right until all needed chars covered; shrink left tracking best.

function minWindow(s, t) {
  if (!t.length) return ''
  const need = new Map()
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1)
  let have = 0,
    goal = need.size,
    left = 0,
    best = '',
    bestLen = Infinity
  const window = new Map()
  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    window.set(c, (window.get(c) ?? 0) + 1)
    if (need.has(c) && window.get(c) === need.get(c)) have++
    while (have === goal) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1
        best = s.slice(left, right + 1)
      }
      const l = s[left++]
      window.set(l, window.get(l) - 1)
      if (need.has(l) && window.get(l) < need.get(l)) have--
    }
  }
  return best
}

Function calls with output

// ── Demo calls — output shown on the right ──
minWindow('ADOBECODEBANC', 'ABC') // → "BANC"
minWindow('a', 'a') // → "a"

Back to index

29. Longest Substring Without Repeating Characters

Difficulty: Medium · Time: O(n) · Space: O(min(n, charset))

Length of longest substring with all unique characters.

Approach (step by step):

Sliding window with last-seen index map; move left past duplicate.

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

Function calls with output

// ── Demo calls — output shown on the right ──
lengthOfLongestSubstring('abcabcbb') // → 3
lengthOfLongestSubstring('bbbbb') // → 1

Back to index

30. Substrings Length K with K-1 Distinct

Difficulty: Medium · Time: O(n) · Space: O(k)

Count substrings of length k with exactly k-1 distinct characters.

Approach (step by step):

Count exactly-k minus exactly-(k-1) distinct substrings of length k.

function substringsKDistinctMinusOne(s, k) {
  const countExact = (d) => {
    const freq = new Map()
    let left = 0,
      total = 0
    for (let right = 0; right < s.length; right++) {
      freq.set(s[right], (freq.get(s[right]) ?? 0) + 1)
      while (freq.size > d) {
        const c = s[left++]
        const f = freq.get(c) - 1
        if (f === 0) freq.delete(c)
        else freq.set(c, f)
      }
      if (right - left + 1 === k && freq.size === d) total++
    }
    return total
  }
  return countExact(k - 1) - countExact(k - 2)
}

Function calls with output

// ── Demo calls — output shown on the right ──
substringsKDistinctMinusOne('abc', 3) // → 1
substringsKDistinctMinusOne('aba', 2) // → 2

Back to index

31. Count Number of Substrings

Difficulty: Medium · Time: O(n) · Space: O(1)

Count total number of non-empty substrings of string s.

Approach (step by step):

Formula: n*(n+1)/2 for length n.

function countSubstrings(s) {
  const n = s.length
  return (n * (n + 1)) / 2
}

Function calls with output

// ── Demo calls — output shown on the right ──
countSubstrings('abc') // → 6
countSubstrings('a') // → 1

Back to index

32. Check Interleaved Strings

Difficulty: Medium · Time: O(n · m) · Space: O(n · m)

Return true if s3 is formed by interleaving s1 and s2 without reordering chars.

Approach (step by step):

2D DP: dp[i][j] true if s3[0..i+j) matches s1[0..i) and s2[0..j).

function isInterleave(s1, s2, s3) {
  if (s1.length + s2.length !== s3.length) return false
  const dp = Array.from({ length: s1.length + 1 }, () => Array(s2.length + 1).fill(false))
  dp[0][0] = true
  for (let i = 0; i <= s1.length; i++) {
    for (let j = 0; j <= s2.length; j++) {
      if (i && s1[i - 1] === s3[i + j - 1]) dp[i][j] ||= dp[i - 1][j]
      if (j && s2[j - 1] === s3[i + j - 1]) dp[i][j] ||= dp[i][j - 1]
    }
  }
  return dp[s1.length][s2.length]
}

Function calls with output

// ── Demo calls — output shown on the right ──
isInterleave('aab', 'axy', 'aaxaby') // → true
isInterleave('aab', 'axy', 'aaaaxy') // → false

Back to index

33. Group Anagrams Together

Difficulty: Medium · Time: O(n · k log k) · Space: O(n · k)

Group strings that are anagrams; return array of groups.

Approach (step by step):

Sort each word as key, bucket into Map, return values.

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

Function calls with output

// ── Demo calls — output shown on the right ──
groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']) // → [["eat","tea","ate"],["tan","nat"],["bat"]]
groupAnagrams(['']) // → [[""]]

Back to index

34. Rank Lexicographic Permutation

Difficulty: Medium · Time: O(n²) · Space: O(n)

Return 1-based lexicographic rank of permutation string of unique chars.

Approach (step by step):

For each position, count smaller unused chars; multiply by factorial remainder.

function lexRank(s) {
  const fact = [1]
  for (let i = 1; i <= s.length; i++) fact[i] = fact[i - 1] * i
  const chars = s.split('').sort()
  let rank = 1
  for (let i = 0; i < s.length; i++) {
    let smaller = 0
    for (const c of chars) {
      if (c === s[i]) break
      smaller++
    }
    rank += smaller * fact[s.length - 1 - i]
    chars.splice(chars.indexOf(s[i]), 1)
  }
  return rank
}

Function calls with output

// ── Demo calls — output shown on the right ──
lexRank('acb') // → 2
lexRank('abc') // → 1
lexRank('bca') // → 4

Back to index

35. Special Keyboard

Difficulty: Medium · Time: O(n · m) · Space: O(n · m)

Minimum key presses to type word: each press prints a char or last printed char again.

Approach (step by step):

DP: dp[i] min presses for prefix; try extend by new char or repeat last.

function specialKeyboard(word) {
  const n = word.length
  const dp = Array(n + 1).fill(Infinity)
  dp[0] = 0
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + 1
    for (let j = 0; j < i - 1; j++) {
      if (word[j] === word[i - 1]) dp[i] = Math.min(dp[i], dp[j] + 1)
    }
  }
  return dp[n]
}

Function calls with output

// ── Demo calls — output shown on the right ──
specialKeyboard('aaaa') // → 2
specialKeyboard('abc') // → 3

Back to index

36. Sum of Two Large Numbers

Difficulty: Medium · Time: O(n) · Space: O(n)

Add two non-negative integers given as strings.

Approach (step by step):

Add digits right-to-left with carry; return result string.

function addLargeNumbers(a, b) {
  let i = a.length - 1,
    j = b.length - 1,
    carry = 0,
    out = ''
  while (i >= 0 || j >= 0 || carry) {
    const sum = (+a[i--] || 0) + (+b[j--] || 0) + carry
    out = (sum % 10) + out
    carry = Math.floor(sum / 10)
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
addLargeNumbers('123', '456') // → "579"
addLargeNumbers('999', '1') // → "1000"

Back to index

Hard (37–50)

37. Repeatedly Remove Adjacent Duplicates

Difficulty: Hard · Time: O(n) · Space: O(n)

Remove all adjacent duplicate pairs repeatedly until no more removals (stack).

Approach (step by step):

Push chars; if top equals current, pop; else push.

function removeDuplicates(s) {
  const stack = []
  for (const c of s) {
    if (stack.length && stack[stack.length - 1] === c) stack.pop()
    else stack.push(c)
  }
  return stack.join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
removeDuplicates('abbaca') // → "ca"
removeDuplicates('azxxzy') // → "ay"

Back to index

38. Multiply Two Strings

Difficulty: Hard · Time: O(n · m) · Space: O(n + m)

Return product of two non-negative integers represented as strings.

Approach (step by step):

Grade-school multiplication into int array; trim leading zeros.

function multiplyStrings(num1, num2) {
  if (num1 === '0' || num2 === '0') return '0'
  const m = num1.length,
    n = num2.length
  const res = Array(m + n).fill(0)
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = +num1[i] * +num2[j]
      const sum = mul + res[i + j + 1]
      res[i + j + 1] = sum % 10
      res[i + j] += Math.floor(sum / 10)
    }
  }
  let i = 0
  while (i < res.length - 1 && res[i] === 0) i++
  return res.slice(i).join('')
}

Function calls with output

// ── Demo calls — output shown on the right ──
multiplyStrings('123', '456') // → "56088"
multiplyStrings('0', '123') // → "0"

Back to index

39. Search Pattern KMP

Difficulty: Hard · Time: O(n + m) · Space: O(m)

Return starting indices of all occurrences of pattern in text using KMP.

Approach (step by step):

Build LPS for pattern; scan text with fallback on mismatch.

function kmpSearch(text, pattern) {
  if (!pattern) return []
  const buildLps = (p) => {
    const lps = Array(p.length).fill(0)
    let len = 0,
      i = 1
    while (i < p.length) {
      if (p[i] === p[len]) {
        len++
        lps[i] = len
        i++
      } else if (len) len = lps[len - 1]
      else {
        lps[i] = 0
        i++
      }
    }
    return lps
  }
  const lps = buildLps(pattern)
  const out = []
  let i = 0,
    j = 0
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++
      j++
    }
    if (j === pattern.length) {
      out.push(i - j)
      j = lps[j - 1]
    } else if (i < text.length && text[i] !== pattern[j]) {
      if (j) j = lps[j - 1]
      else i++
    }
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
kmpSearch('ababcababa', 'aba') // → [0, 5, 7]
kmpSearch('aaaa', 'aa') // → [0, 1, 2]

Back to index

40. Search Pattern Rabin-Karp

Difficulty: Hard · Time: O(n + m) avg · Space: O(1)

Find all starting indices of pattern in text using rolling hash (Rabin-Karp).

Approach (step by step):

Compare hash of window; verify on match; roll hash each step.

function rabinKarp(text, pattern) {
  if (!pattern.length || pattern.length > text.length) return []
  const base = 256,
    mod = 1e9 + 7
  const m = pattern.length,
    n = text.length
  let pHash = 0,
    tHash = 0,
    h = 1
  for (let i = 0; i < m - 1; i++) h = (h * base) % mod
  const out = []
  for (let i = 0; i < m; i++) {
    pHash = (pHash * base + pattern.charCodeAt(i)) % mod
    tHash = (tHash * base + text.charCodeAt(i)) % mod
  }
  for (let i = 0; i <= n - m; i++) {
    if (pHash === tHash && text.slice(i, i + m) === pattern) out.push(i)
    if (i < n - m) tHash = (base * (tHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod
    if (tHash < 0) tHash += mod
  }
  return out
}

Function calls with output

// ── Demo calls — output shown on the right ──
rabinKarp('abababa', 'aba') // → [0, 2, 4]
rabinKarp('hello', 'll') // → [2]

Back to index

41. Shortest Common Supersequence Length

Difficulty: Hard · Time: O(n · m) · Space: O(n · m)

Minimum length of string containing both a and b as subsequences.

Approach (step by step):

LCS DP; answer = len(a) + len(b) - LCS length.

function scsLength(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => Array(b.length + 1).fill(0))
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1])
    }
  }
  return a.length + b.length - dp[a.length][b.length]
}

Function calls with output

// ── Demo calls — output shown on the right ──
scsLength('abac', 'cab') // → 5
scsLength('abc', 'abc') // → 3

Back to index

42. Longest Substring to Form Palindrome

Difficulty: Hard · Time: O(n²) · Space: O(1)

Return true if some substring of s can be rearranged into a palindrome.

Approach (step by step):

Check every substring frequency parity — at most one odd count allowed.

function canFormPalindromeSubstring(s) {
  const n = s.length
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      const cnt = Array(26).fill(0)
      let odds = 0
      for (let k = i; k <= j; k++) {
        const idx = s.charCodeAt(k) - 97
        cnt[idx]++
        if (cnt[idx] % 2 === 1) odds++
        else odds--
      }
      if (odds <= 1) return true
    }
  }
  return false
}

Function calls with output

// ── Demo calls — output shown on the right ──
canFormPalindromeSubstring('aabb') // → true
canFormPalindromeSubstring('abc') // → true
canFormPalindromeSubstring('abcabc') // → true

Back to index

43. Longest Valid Parentheses

Difficulty: Hard · Time: O(n) · Space: O(n)

Length of longest well-formed parentheses substring.

Approach (step by step):

Stack stores last invalid index; update max on match.

function longestValidParentheses(s) {
  const stack = [-1]
  let best = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') stack.push(i)
    else {
      stack.pop()
      if (!stack.length) stack.push(i)
      else best = Math.max(best, i - stack[stack.length - 1])
    }
  }
  return best
}

Function calls with output

// ── Demo calls — output shown on the right ──
longestValidParentheses('(()') // → 2
longestValidParentheses(')()())') // → 4

Back to index

44. Longest Palindromic Subsequence Length

Difficulty: Hard · Time: O(n²) · Space: O(n²)

Length of longest palindromic subsequence (not necessarily contiguous).

Approach (step by step):

DP on intervals: match ends +2, else max of skip left or right end.

function lpsSubseq(s) {
  const n = s.length
  const dp = Array.from({ length: n }, () => Array(n).fill(0))
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1])
    }
  }
  return dp[0][n - 1]
}

Function calls with output

// ── Demo calls — output shown on the right ──
lpsSubseq('bbbab') // → 4
lpsSubseq('cbbd') // → 2

Back to index

45. Count Distinct Palindromic Substrings

Difficulty: Hard · Time: O(n²) · Space: O(n²)

Count distinct palindromic substrings in s.

Approach (step by step):

Expand around each center; add to Set; return size.

function countDistinctPalindromes(s) {
  const set = new Set()
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      set.add(s.slice(l, r + 1))
      l--
      r++
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i)
    expand(i, i + 1)
  }
  return set.size
}

Function calls with output

// ── Demo calls — output shown on the right ──
countDistinctPalindromes('abaaa') // → 5
countDistinctPalindromes('abc') // → 3

Back to index

46. Palindrome Substring Queries

Difficulty: Hard · Time: O(n² + q) · Space: O(n²)

Precompute palindrome substrings; answer count of palindrome substrings in range [l, r] (0-indexed, inclusive).

Approach (step by step):

2D boolean DP for palindrome substrings; prefix sum per start index for queries.

function palindromeQueries(s, queries) {
  const n = s.length
  const isPal = Array.from({ length: n }, () => Array(n).fill(false))
  for (let i = n - 1; i >= 0; i--) {
    isPal[i][i] = true
    for (let j = i + 1; j < n; j++) {
      isPal[i][j] = s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1])
    }
  }
  return queries.map(([l, r]) => {
    let count = 0
    for (let i = l; i <= r; i++) {
      for (let j = i; j <= r; j++) if (isPal[i][j]) count++
    }
    return count
  })
}

Function calls with output

// ── Demo calls — output shown on the right ──
palindromeQueries('aba', [[0, 2]]) // → [4]
palindromeQueries('aaa', [
  [0, 1],
  [0, 2],
]) // → [3, 6]

Back to index

47. Number of Distinct Subsequences

Difficulty: Hard · Time: O(n · m) · Space: O(m)

Count distinct subsequences of s equal to t.

Approach (step by step):

DP: if chars match add dp[j-1], always add dp[j] from prev row.

function numDistinct(s, t) {
  const m = t.length
  let dp = Array(m + 1).fill(0)
  dp[0] = 1
  for (const c of s) {
    for (let j = m - 1; j >= 0; j--) {
      if (c === t[j]) dp[j + 1] += dp[j]
    }
  }
  return dp[m]
}

Function calls with output

// ── Demo calls — output shown on the right ──
numDistinct('rabbbit', 'rabbit') // → 3
numDistinct('babgbag', 'bag') // → 5

Back to index

48. Minimum Deletions for Palindrome

Difficulty: Hard · Time: O(n²) · Space: O(n²)

Minimum deletions to make string a palindrome.

Approach (step by step):

Answer = n - LPS length (longest palindromic subsequence).

function minDeletionsPalindrome(s) {
  const n = s.length
  const dp = Array.from({ length: n }, () => Array(n).fill(0))
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1])
    }
  }
  return n - dp[0][n - 1]
}

Function calls with output

// ── Demo calls — output shown on the right ──
minDeletionsPalindrome('aebcbda') // → 2
minDeletionsPalindrome('abc') // → 2

Back to index

49. Minimum Insertions for Palindrome

Difficulty: Hard · Time: O(n²) · Space: O(n²)

Minimum insertions to make string a palindrome.

Approach (step by step):

Same as deletions: n - longest palindromic subsequence length.

function minInsertionsPalindrome(s) {
  const n = s.length
  const dp = Array.from({ length: n }, () => Array(n).fill(0))
  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] + 2 : Math.max(dp[i + 1][j], dp[i][j - 1])
    }
  }
  return n - dp[0][n - 1]
}

Function calls with output

// ── Demo calls — output shown on the right ──
minInsertionsPalindrome('abcd') // → 3
minInsertionsPalindrome('a') // → 0

Back to index

50. Max Non-Overlapping Odd Palindrome Sum

Difficulty: Hard · Time: O(n²) · Space: O(n²)

Maximum sum of values at centers of non-overlapping odd-length palindrome substrings (simplified: sum digit values).

Approach (step by step):

Find all odd palindromes with prefix sums; DP pick non-overlapping max sum.

function maxOddPalindromeSum(s) {
  const n = s.length
  const vals = [...s].map((c) => +c || 0)
  const pals = []
  for (let center = 0; center < n; center++) {
    let l = center,
      r = center,
      sum = vals[center]
    while (l >= 0 && r < n && s[l] === s[r]) {
      if (l !== center || r !== center) sum += vals[l] + vals[r]
      pals.push({ l, r, sum })
      l--
      r++
    }
  }
  pals.sort((a, b) => a.r - b.r)
  const dp = Array(pals.length).fill(0)
  for (let i = 0; i < pals.length; i++) {
    dp[i] = pals[i].sum
    for (let j = 0; j < i; j++) {
      if (pals[j].r < pals[i].l) dp[i] = Math.max(dp[i], dp[j] + pals[i].sum)
    }
    if (i) dp[i] = Math.max(dp[i], dp[i - 1])
  }
  return dp.at(-1) ?? 0
}

Function calls with output

// ── Demo calls — output shown on the right ──
maxOddPalindromeSum('12321') // → 15
maxOddPalindromeSum('111') // → 2

Back to index

Summary

Level	Count	Patterns
Easy	13	Two pointers, frequency maps, parsing
Medium	23	Sliding window, Dutch flag, DP interleaving
Hard	14	KMP, Rabin-Karp, palindrome DP, subsequence DP