String Logic Problems

A palindrome reads the same forwards and backwards (e.g., "racecar", "level"). The simplest check: compare the string with its reverse.

The two-pointer approach is O(1) extra space: use pointers at both ends, move toward center comparing characters. Stop when they meet or mismatch.

For real-world palindrome problems, also handle case-insensitivity and ignore non-alphanumeric characters.

// Method 1: reverse comparison
function isPalindrome(s) {
  const low = s.toLowerCase();
  return low === low.split('').reverse().join('');
}

// Method 2: two-pointer (no extra space)
function isPalindromeTP(s) {
  s = s.toLowerCase();
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return false;
    l++; r--;
  }
  return true;
}
// isPalindrome("racecar") => true
// isPalindrome("hello")   => false

Two-pointer is O(1) space and O(n/2) comparisons (stops at the midpoint).

Even-length palindromes ("abba") and odd-length ("aba") both work with the same two-pointer logic.

Two strings are anagrams if they contain the same characters with the same frequencies, just in different order ("listen" and "silent" are anagrams).

Approach 1: sort both strings and compare — O(n log n). Approach 2: character frequency map — O(n). For constraints requiring O(n), use the frequency map.

Always check lengths first — different lengths are immediately not anagrams.

// Sort approach: O(n log n)
function isAnagram(a, b) {
  const sort = s => s.toLowerCase().split('').sort().join('');
  return a.length === b.length && sort(a) === sort(b);
}

// Frequency map: O(n) time, O(1) space (fixed alphabet)
function isAnagramFast(a, b) {
  if (a.length !== b.length) return false;
  const count = Array(26).fill(0);
  for (let i = 0; i < a.length; i++) {
    count[a.charCodeAt(i) - 97]++;
    count[b.charCodeAt(i) - 97]--;
  }
  return count.every(v => v === 0);
}
// isAnagram("listen", "silent") => true
// isAnagram("hello",  "world")  => false

Frequency map is O(n) vs O(n log n) for sorting. For large strings or performance-critical code, frequency map is preferred.

Unicode support: plain charCode approach only works for ASCII. For full Unicode, use a Map instead of a fixed-size array.

Vowels in English are a, e, i, o, u (and sometimes y). To count them, use regex to match all vowel characters globally, or loop through checking a Set membership.

The regex approach is concise and handles both upper and lower case with the gi flags. The loop approach is more readable for beginners.

Counting vowels is often a foundation of more complex string problems like finding the longest vowel substring.

// Regex approach
function countVowels(s) {
  return (s.match(/[aeiou]/gi) || []).length;
}

// Loop approach (explicit)
function countVowelsLoop(s) {
  const vowels = new Set('aeiouAEIOU');
  let count = 0;
  for (const c of s) if (vowels.has(c)) count++;
  return count;
}
// countVowels("Hello World") => 3 (e, o, o)
// countVowels("bcdfg")       => 0
// countVowels("Beautiful")   => 5

regex .match().length returns null if no matches — always use || [] as fallback to avoid TypeError.

For finding vowels vs consonants ratio or extracting only vowels, the loop approach with Set is more flexible.

Build a frequency map in one pass, then do a second pass to find the first character with count exactly 1. Two passes, O(n) total time.

This maintains the original ORDER of characters — we return the first one that appears only once.

A one-pass Set/array approach stores order too: add to Set (first seen), move to separate Set (seen twice). Return first in first-seen Set that's not in double-seen.

function firstNonRepeating(s) {
  const freq = {};
  for (const c of s) freq[c] = (freq[c] || 0) + 1; // count all
  for (const c of s) if (freq[c] === 1) return c;   // first count-1
  return null; // all characters repeat
}
// firstNonRepeating("aabbcde") => "c"
// firstNonRepeating("aabb")    => null
// firstNonRepeating("leetcode") => "l"

Two-pass approach is clean and O(n) — first pass counts, second pass finds first non-repeat in original order.

Amazon/Google interview variant: streaming version where characters arrive one at a time and you must always return the current first non-repeating.

Split the sentence by spaces (or whitespace) to get individual words, then find the word with maximum length using reduce or Math.max on the lengths array.

The reduce approach is clean and O(n) — compare each word length, keep the longer one as the accumulator.

Handle edge cases: empty string, multiple spaces between words (use regex split), punctuation attached to words.

function longestWord(s) {
  return s.split(/s+/).reduce((a, b) => a.length >= b.length ? a : b);
}

// If you need all longest words (in case of ties):
function allLongestWords(s) {
  const words = s.split(/s+/);
  const maxLen = Math.max(...words.map(w => w.length));
  return words.filter(w => w.length === maxLen);
}
// longestWord("The quick brown fox") => "quick"
// longestWord("I love JavaScript")   => "JavaScript"

Use /s+/ regex (not just ' ') to handle multiple consecutive spaces correctly.

If multiple words share the maximum length, the reduce approach returns the FIRST one (due to >= comparison).

Split the string by spaces, transform each word by uppercasing its first character and keeping the rest unchanged, then join back with spaces.

This is called "Title Case" formatting. The two-step split-map-join pattern is clean and idiomatic JavaScript.

Consider edge cases: empty words from multiple spaces (filter them), words that are already capitalized, all-uppercase words.

function capitalizeWords(s) {
  return s.split(' ')
    .map(w => w ? w[0].toUpperCase() + w.slice(1) : w)
    .join(' ');
}

// Using regex (single expression):
function capitalizeRegex(s) {
  return s.replace(/w/g, c => c.toUpperCase());
}
// capitalizeWords("hello world") => "Hello World"
// capitalizeWords("the quick brown fox") => "The Quick Brown Fox"

w regex matches word boundaries followed by a word character — handles all word separators, not just spaces.

Note: .slice(1) preserves rest of word unchanged. Using .toLowerCase() first ensures only the first letter is capitalized.

The ES6 Set automatically stores only unique values. Converting a string to a Set via spread/Array.from removes duplicate characters while preserving insertion order (first occurrence only).

This is idiomatic modern JavaScript. For older environments or explicit character order control, use a seen-object approach.

The result preserves the FIRST occurrence of each character in original order.

// ES6 Set approach (idiomatic)
function removeDuplicates(s) {
  return [...new Set(s)].join('');
}

// Explicit approach (same result)
function removeDupsExplicit(s) {
  const seen = new Set();
  let result = '';
  for (const c of s) {
    if (!seen.has(c)) { seen.add(c); result += c; }
  }
  return result;
}
// removeDuplicates("aabbccdde")  => "abcde"
// removeDuplicates("hello")      => "helo"
// removeDuplicates("programming") => "progamin"

Set preserves insertion order in JavaScript — first occurrence is kept, subsequent duplicates are dropped.

If the order doesn't matter, sorting first then removing consecutive duplicates is another option (but changes order).

Run-length encoding (RLE): scan left to right counting consecutive identical characters. When a new character is encountered, emit the previous character + count (omit count if 1).

This is a simple lossless compression technique — effective only when strings have many consecutive repeats.

Common variant: only return the compressed form if shorter than original; otherwise return original.

function compress(s) {
  let result = '', count = 1;
  for (let i = 1; i <= s.length; i++) {
    if (i < s.length && s[i] === s[i - 1]) {
      count++;
    } else {
      result += s[i - 1] + (count > 1 ? count : '');
      count = 1;
    }
  }
  return result.length < s.length ? result : s;
}
// compress("aabcccdddd") => "a2bc3d4"
// compress("abcd")       => "abcd" (no compression benefit)
// compress("aaabbb")     => "a3b3"

Loop to length (inclusive) — the i <= s.length condition ensures the LAST group is emitted.

The comparison result.length < s.length at the end implements the "only compress if beneficial" requirement.

A frequency map (object or Map) counts how many times each character appears. This is the foundation for many string problems: anagram detection, most frequent character, etc.

After building the map, convert to entries for sorting or filtering. Use Object.entries() with array methods.

ES6 Map preserves insertion order and handles all character types (including emoji) better than plain objects.

function charFrequency(s) {
  const freq = {};
  for (const c of s) freq[c] = (freq[c] || 0) + 1;
  return freq;
}
// charFrequency("hello") => {h:1, e:1, l:2, o:1}

// Most frequent character:
function mostFrequent(s) {
  const freq = charFrequency(s);
  return Object.entries(freq).sort(([,a],[,b]) => b - a)[0][0];
}
// mostFrequent("aabbbcccc") => "c"

Frequency maps are useful for anagram checks: two strings are anagrams if their frequency maps are identical.

For character frequency problems, consider if spaces/punctuation should be included — often they should be excluded first.

Use the sliding window technique with a Set tracking characters in the current window. Expand the right pointer; when a duplicate is found, shrink from the left until the duplicate is removed.

The window always contains unique characters. Track the maximum window size seen. This is a classic O(n) sliding window pattern.

Alternative: store character index in a Map for O(1) jumps when encountering duplicates.

function lengthOfLongestSubstring(s) {
  let set = new Set(), l = 0, maxLen = 0;
  for (let r = 0; r < s.length; r++) {
    while (set.has(s[r])) set.delete(s[l++]); // shrink window
    set.add(s[r]);
    maxLen = Math.max(maxLen, r - l + 1);
  }
  return maxLen;
}
// lengthOfLongestSubstring("abcabcbb") => 3 ("abc")
// lengthOfLongestSubstring("bbbbb")   => 1 ("b")
// lengthOfLongestSubstring("pwwkew")  => 3 ("wke")

Sliding window gives O(n) time and O(min(m,n)) space where m is the character set size.

The Map-based variant skips directly: when s[r] is in map at index i, jump l to max(l, i+1) — avoids repeated deletions.

Use backtracking: swap the current character with each remaining character, recurse, then swap back (restore state). When the index reaches the end, save the current permutation.

A string of n unique characters has n! permutations. Handling duplicates requires sorting and skipping already-used characters.

Iterative approach: start with first character, insert it at every position of each existing permutation.

function permutations(str) {
  const result = [];
  function backtrack(arr, start) {
    if (start === arr.length) { result.push(arr.join('')); return; }
    for (let i = start; i < arr.length; i++) {
      [arr[start], arr[i]] = [arr[i], arr[start]]; // swap
      backtrack(arr, start + 1);
      [arr[start], arr[i]] = [arr[i], arr[start]]; // undo swap
    }
  }
  backtrack(str.split(''), 0);
  return result;
}
// permutations("abc") => ["abc","acb","bac","bca","cba","cab"] (3!=6)

Time O(n! * n) — n! permutations each taking O(n) to copy. This is unavoidable since the output itself is that large.

For large strings, generating all permutations is impractical. Next permutation (lexicographic) is a better approach for some problems.

A clever trick: if s2 is a rotation of s1, then s2 must appear as a substring in s1+s1. This works because concatenating s1 with itself contains all possible rotations of s1.

First verify lengths are equal, then use includes() or KMP search for the concatenation approach.

Example: "rotation" of "abcde" — "cdeab" appears in "abcdeabcde".

function isRotation(s1, s2) {
  if (s1.length !== s2.length) return false;
  return (s1 + s1).includes(s2);
}
// isRotation("abcde", "cdeab") => true  ("cdeab" in "abcdeabcde")
// isRotation("abcde", "abced") => false (different characters rearranged)

One includes() check replaces the need to try all rotation positions. O(n) time with efficient string search.

This works because s1+s1 contains EVERY possible rotation of s1 as a substring.

Start with "1". Each subsequent term describes the previous term by counting consecutive groups of digits. "1" → "11" (one 1) → "21" (two 1s) → "1211" (one 2, one 1).

To build each term: scan previous term, count consecutive identical digits, then append count + digit to result.

This is an iterative string generation problem — no math formula, just string processing.

function countAndSay(n) {
  let result = '1';
  for (let i = 1; i < n; i++) {
    let next = '', count = 1;
    for (let j = 1; j <= result.length; j++) {
      if (j < result.length && result[j] === result[j-1]) {
        count++;
      } else {
        next += count + result[j-1];
        count = 1;
      }
    }
    result = next;
  }
  return result;
}
// countAndSay(1) => "1"
// countAndSay(4) => "1211"
// countAndSay(5) => "111221"

Sequence: 1 → 11 → 21 → 1211 → 111221 → 312211 → ...

This sequence only ever contains 1s, 2s, and 3s — no run of identical digits can exceed 3.

Sliding window with two frequency maps: one for the pattern (required) and one for the current window. Track how many pattern characters are fully satisfied (have count ≥ required).

Expand right until window is valid (all pattern chars covered), then shrink from left to find minimum valid window. Track minimum seen so far.

This hard sliding window pattern appears in many interview problems requiring "minimum window" solutions.

function minWindow(s, t) {
  const need = {}, window = {};
  for (const c of t) need[c] = (need[c] || 0) + 1;
  let have = 0, required = Object.keys(need).length;
  let l = 0, minLen = Infinity, result = '';
  for (let r = 0; r < s.length; r++) {
    const c = s[r];
    window[c] = (window[c] || 0) + 1;
    if (need[c] && window[c] === need[c]) have++;
    while (have === required) {
      if (r - l + 1 < minLen) { minLen = r - l + 1; result = s.slice(l, r+1); }
      window[s[l]]--;
      if (need[s[l]] && window[s[l]] < need[s[l]]) have--;
      l++;
    }
  }
  return result;
}
// minWindow("ADOBECODEBANC", "ABC") => "BANC"

Time O(|s|+|t|) — each character is visited at most twice (once by r, once by l).

Track have (satisfied char types) vs required (total char types in pattern) to efficiently determine window validity.

Group strings that are anagrams of each other. Key insight: anagrams produce the same string when sorted. Use sorted string as the map key to group anagrams together.

Build a Map where each key is the sorted version of a string. Push each original string into its group. Return all values.

Alternative key: character frequency array (better for unicode) — concatenate as "a2b1..." style string.

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()];
}
// groupAnagrams(["eat","tea","tan","ate","nat","bat"])
// => [["eat","tea","ate"],["tan","nat"],["bat"]]

Sorted string as key is O(k log k) per string where k is string length. Total: O(n * k log k).

Character count key (26-element array stringified) gives O(n * k) total — faster for long strings with small alphabets.

Find the first index of needle in haystack. Return -1 if not found. This is the indexOf / substring search problem.

Naive O(n*m) approach: try starting at each position in haystack, check if needle matches. Works for most cases.

KMP (Knuth-Morris-Pratt) gives O(n+m) by pre-computing a failure function to skip re-comparing known matches.

// Naive approach: O(n*m)
function strStr(haystack, needle) {
  if (!needle) return 0;
  for (let i = 0; i <= haystack.length - needle.length; i++) {
    if (haystack.substring(i, i + needle.length) === needle) return i;
  }
  return -1;
}
// OR built-in:
// haystack.indexOf(needle)

// strStr("hello", "ll")   => 2
// strStr("aaaaa", "bba")  => -1
// strStr("", "")          => 0

Built-in indexOf is optimized and should be used in production. Implement manually only when explicitly required.

For pattern matching with wildcards or regex, use different algorithms (like Rabin-Karp or Aho-Corasick).

Implement parseInt-like parsing: skip leading whitespace, handle optional sign (+/-), read digits until non-digit, clamp to 32-bit integer range.

This problem is often about careful edge case handling rather than algorithm complexity.

Common edge cases: leading/trailing spaces, sign character, non-digit characters mid-number, overflow.

function myAtoi(s) {
  s = s.trimStart();
  if (!s) return 0;
  let sign = 1, i = 0, result = 0;
  const INT_MAX = 2**31 - 1, INT_MIN = -(2**31);
  if (s[0] === '-') { sign = -1; i++; }
  else if (s[0] === '+') i++;
  while (i < s.length && s[i] >= '0' && s[i] <= '9') {
    result = result * 10 + Number(s[i++]);
    if (result * sign > INT_MAX) return INT_MAX;
    if (result * sign < INT_MIN) return INT_MIN;
  }
  return result * sign;
}
// myAtoi("   -42")      => -42
// myAtoi("4193 words")  => 4193
// myAtoi("words 987")   => 0

Stop on first non-digit after leading whitespace and sign — don't skip non-digits mid-number.

Clamp to [-2³¹, 2³¹-1] range, checking overflow DURING digit accumulation to avoid JavaScript large integer issues.

Split the string by spaces, reverse the array of words, and rejoin. Handle multiple spaces by filtering empty strings from split.

For in-place reversal (C-style): reverse the entire string first, then reverse each word individually.

Be aware of edge cases: leading/trailing spaces, multiple consecutive spaces between words.

function reverseWords(s) {
  return s.trim().split(/s+/).reverse().join(' ');
}
// reverseWords("the sky is blue") => "blue is sky the"
// reverseWords("  hello world  ") => "world hello"
// reverseWords("a good  example") => "example good a"

// In-place double-reverse approach (no split):
// 1. Reverse entire string: "eulb si yks eht"
// 2. Reverse each word:     "blue is sky the"

/s+/ regex handles multiple spaces between words and the .trim() removes leading/trailing.

The double-reverse in-place approach is useful for fixed-size character arrays (like in C/C++) where extra space is not allowed.

Find every starting index where a pattern occurs in a text. The naive approach checks every position. Rabin-Karp uses rolling hash for O(n+m) expected time.

For fixed-size patterns, sliding window with character frequency comparison gives O(n) time — reuse the count from the previous position.

This is the foundation of grep, code editors' Find functions, and DNA sequence matching.

// Find all anagram occurrences of pattern in string
function findAllOccurrences(s, p) {
  const result = [], need = Array(26).fill(0), window = Array(26).fill(0);
  const a = 'a'.charCodeAt(0);
  for (const c of p) need[c.charCodeAt(0) - a]++;
  for (let i = 0; i < s.length; i++) {
    window[s[i].charCodeAt(0) - a]++;
    if (i >= p.length) window[s[i-p.length].charCodeAt(0) - a]--;
    if (window.every((v, j) => v === need[j])) result.push(i - p.length + 1);
  }
  return result;
}
// findAllOccurrences("cbaebabacd", "abc") => [0, 6]

Sliding window with frequency arrays gives O(n) by avoiding recount from scratch for each position.

This pattern (find all anagram positions) is LeetCode #438 and a common sliding window interview question.