SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 14
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 14 of 30

String questions IV

longest substring without repeating characters (sliding window)string compression (aabccc → a2b1c3)valid parentheses with a stack

These are the notes for JavaScript Coding Questions, episode 14, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three of the most asked string questions, each with a classic tool: the longest substring without repeating characters (a sliding window), string compression aabccc → a2b1c3 (a run counter), and valid parentheses (a stack).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Plain modern JavaScript, no packages.

About the timings. Lines like brute: 2.286s are copied from a real run on one machine; your numbers will differ. What matters is the size of the gap.

Q1: Longest substring without repeating characters

Problem. Return the length of the longest substring (a piece of the string with no gaps) in which no character repeats.

"abcabcbb" → 3   ("abc")
"bbbbb"    → 1   ("b")
"pwwkew"   → 3   ("wke"; "pwke" skips a character, so it is not a substring)
"abba"     → 2   ("ab" or "ba")
"dvdf"     → 3   ("vdf")
""         → 0

Real life: the longest stretch of a playlist in which no song plays twice.

Think out loud

  • Substring means consecutive characters. A subsequence may skip characters; that is a different question.
  • Edge cases: all the same character, empty string, a repeat far back (abba), long input.

The obvious attempt: check every substring

function longest(s) {
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      const part = s.slice(i, j + 1);
      if (new Set(part).size === part.length) best = Math.max(best, part.length);
    }
  }
  return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
const codes = Array.from({ length: 600 }, (_, i) => 0x4e00 + i);
const big = String.fromCharCode(...codes);
console.time("brute");
console.log(longest(big));
console.timeEnd("brute");
3 1 3
600
brute: 1.936s

Correct, but seconds for 600 characters. There are about n²/2 substrings, and building a Set from each costs up to n more: O(n³) time. Double the input and it becomes about eight times slower. (String.fromCharCode(...codes) builds a string from character codes; codes from 0x4e00 are 600 different Chinese characters, so nothing repeats.)

The idea: a sliding window (a playlist with no repeats)

Keep a window s[left..right] with no repeats.

  1. Each step, right moves forward one character (the next song joins).
  2. If that character is already in the window, left jumps to one past its earlier position (drop songs up to the earlier play).
  3. A Map last remembers the last position of each character, so the jump is instant.

Both ends only move forward, so the whole string is walked once.

First window, and the abba trap

function longest(s) {
  const last = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c)) left = last.get(c) + 1;
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
console.log(longest("abba"));
3 1 3
3

abba should be 2. At the second b (index 2), left becomes 2. At the last a (index 3), last.get("a") is 0, which is already outside the window, but left = 0 + 1 moves left back to 1. The window bba is counted, with b twice.

Fix: left never moves back

function longest(s) {
  const last = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (last.has(c)) left = Math.max(left, last.get(c) + 1);
    last.set(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
console.log(longest("abba"), longest("dvdf"), longest(""));

const big = "abcdefghijklmnopqrstuvwxyz".repeat(40000);
console.time("window");
console.log(big.length, longest(big));
console.timeEnd("window");
3 1 3
2 3 0
1040000 26
window: 30.823ms

Complexity: O(n) time (right moves n times, left only forward); O(k) space for the Map, where k is the number of different characters.

Q2: String compression

Problem. Write each run (consecutive equal characters) as the character followed by its length.

"aabccc"  → "a2b1c3"
"aabccaa" → "a2b1c2a2"   (the final a's are a new run)
"a"       → "a1"
""        → ""

Real life: a waiter calling out "2 roti, 1 dal, 3 chai" instead of every plate.

The obvious attempt: a counting Map

function compress(s) {
  const count = new Map();
  for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
  let out = "";
  for (const [c, n] of count) out += c + n;
  return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
a2b1c3
a4b1c2

A Map counts all the as in the whole string and forgets where they were. Compression needs runs: compare each character with the one before it.

Runs, and the lost last run

function compress(s) {
  let out = "", run = 1;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) run++;
    else { out += s[i - 1] + run; run = 1; }
  }
  return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
a2b1
a2b1c2

A run is written only when a different character arrives. The last run is never followed by one, so it is never written: an off-by-one error.

Fix: one more step, i <= s.length

s[s.length] is undefined, which is different from every character, so the extra step closes the last run. For "" the loop never runs and the answer is "".

function compress(s) {
  let out = "", run = 1;
  for (let i = 1; i <= s.length; i++) {
    if (s[i] === s[i - 1]) run++;
    else { out += s[i - 1] + run; run = 1; }
  }
  return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
console.log(JSON.stringify(compress("a")), JSON.stringify(compress("")));
console.log(compress("abc"));
const big = "ab".repeat(500000) + "c".repeat(1000000);
console.time("compress");
console.log(compress(big).length);
console.timeEnd("compress");
a2b1c3
a2b1c2a2
"a1" ""
a1b1c1
2000008
compress: 97.691ms

"abc" becomes "a1b1c1", longer than the input. A common follow-up: return the original when the compressed string is not shorter (practice question 2).

Complexity: one pass, O(n) time; O(n) space for the output.

Q3: Are the brackets balanced?

Problem. Every (, [ and { must be closed by the same kind, in the right order (nesting is fine). Other characters are ignored.

"()[]{}"  → true
"{[()]}"  → true
"(("      → false   (never closed)
"([)]"    → false   (wrong order)
")("      → false   (a close with nothing open)
""        → true
"if (a[0] > 1) { log(a); }" → true
"if (a[0] > 1) { log(a; }"  → false

Real life: your code editor marking a missing bracket in red.

The obvious attempt: one counter

function isValid(s) {
  let open = 0;
  for (const c of s) {
    if ("([{".includes(c)) open++;
    else open--;
  }
  return open === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
true true
false true true

Stopping when the counter goes below zero fixes )(:

function isValid(s) {
  let open = 0;
  for (const c of s) {
    if ("([{".includes(c)) open++;
    else open--;
    if (open < 0) return false;
  }
  return open === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
true true
false true false

But ([)] is still true: a counter knows how many brackets are open, not which ones or in what order.

The idea: a stack (boxes inside boxes)

A stack is a pile where you add and remove only at the top: last in, first out (LIFO). In JavaScript an array is a stack: push adds to the end, pop removes and returns the last item (or undefined if the array is empty).

  • Opening bracket: push it (open a box, put it on top).
  • Closing bracket: pop the top; it must be the matching opener (only the top box can be closed).
  • At the end the stack must be empty (every box closed).
function isValid(s) {
  const pair = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if ("([{".includes(c)) stack.push(c);
    else if (stack.pop() !== pair[c]) return false;
  }
  return stack.length === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
console.log(isValid(""), isValid("]"));
console.log(isValid("if (a[0] > 1) { log(a); }"));
true true
false false false
true false
false

Every bracket-only test is right, and a lone ] is false because [].pop() is undefined. But real code returns false: every non-opener goes to the else, so the letter i pops the stack.

Fix: only closing brackets pop

function isValid(s) {
  const pair = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const c of s) {
    if ("([{".includes(c)) stack.push(c);
    else if (c in pair && stack.pop() !== pair[c]) return false;
  }
  return stack.length === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
console.log(isValid(""), isValid("]"));
console.log(isValid("if (a[0] > 1) { log(a); }"));
console.log(isValid("if (a[0] > 1) { log(a; }"));
true true
false false false
true false
true
false

c in pair is true only for ), ] and }. Thanks to &&, pop runs only for them (short-circuit evaluation).

Complexity: O(n) time; O(n) space in the worst case (all openers).

Complexity summary

Question Approach Time Extra space
Longest substring every substring + Set O(n³) O(n)
Longest substring sliding window + Map of last positions O(n) O(k)
Compression counting Map O(n), and wrong O(k)
Compression run counter, i <= s.length O(n) O(n) output
Brackets one counter O(n), and wrong O(1)
Brackets stack O(n) O(n)

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
Checking every substring two loops + new Set(part) brute: 1.936s for 600 characters O(n³) sliding window
left moving back left = last.get(c) + 1 3 for "abba" the old position may be outside the window Math.max(left, last.get(c) + 1)
Substring vs subsequence counting pwke 4 instead of 3 a substring has no gaps only consecutive characters
Counting instead of runs a counting Map a4b1c2 for "aabccaa" counts lose position compare with s[i - 1]
Off-by-one i < s.length a2b1 for "aabccc" the last run is never closed i <= s.length
Compressing longer always return out a1b1c1 for "abc" single runs double the length compare lengths
One counter for brackets open++ / open-- true for "([)]" and ")(" it forgets which bracket, and order a stack
Popping on every character else if (stack.pop() !== ...) false for real code letters pop the stack c in pair && ...
Forgetting the final check return true true for "((" openers left on the stack stack.length === 0

Mini project: attendance by SMS

A school sends each month's attendance (P present, A absent, L leave) to parents by SMS, where every character counts. Compress it, check that it decodes back to exactly the same string, and report the longest present streak.

// Mini project: send a month's attendance in a short SMS, and read it back
function compress(s) {
  let out = "", run = 1;
  for (let i = 1; i <= s.length; i++) {
    if (s[i] === s[i - 1]) run++;
    else { out += s[i - 1] + run; run = 1; }
  }
  return out;
}
const decompress = s => s.replace(/(\D)(\d+)/g, (m, c, n) => c.repeat(Number(n)));
function longestStreak(s, mark) {
  let best = 0, run = 0;
  for (const c of s) { run = c === mark ? run + 1 : 0; best = Math.max(best, run); }
  return best;
}
const month = "PPPPPPAPPPPPPPPPPPLLPPPPPPPPPP";
const sms = compress(month);
console.log(sms, sms.length, "vs", month.length);
console.log(decompress(sms) === month);
console.log("longest present streak:", longestStreak(month, "P"));
P6A1P11L2P10 12 vs 30
true
longest present streak: 11

This is run-length encoding, used for real in fax machines, simple image formats and in game level data.

Your turn: decompress (solution)

decompress("a2b1c3") → "aabccc", and a count can have several digits: decompress("x12") is twelve xs.

Solution

(\D) is one character that is not a digit (group 1), (\d+) is one or more digits (group 2). The callback repeats the character; Number(n) turns the digits into a number.

const decompress = s => s.replace(/(\D)(\d+)/g, (m, c, n) => c.repeat(Number(n)));
console.log(decompress("a2b1c3"));
console.log(decompress("x12"));
console.log(JSON.stringify(decompress("")));
aabccc
xxxxxxxxxxxx
""

O(m) time and space, where m is the length of the output.

Practice questions (with solutions)

1. Compress only if shorter.

Solution
function compressIfShorter(s) {
  let out = "", run = 1;
  for (let i = 1; i <= s.length; i++) {
    if (s[i] === s[i - 1]) run++;
    else { out += s[i - 1] + run; run = 1; }
  }
  return out.length < s.length ? out : s;
}
console.log(compressIfShorter("aaabbbbcc"), compressIfShorter("abc"), compressIfShorter("aab"));
a3b4c2 abc aab

2. Longest substring with at most 2 different characters.

Solution

A sliding window with a counting Map: grow on the right; while the window has more than 2 different characters, shrink from the left (decrease the count, delete it at 0).

function longestTwo(s) {
  const count = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) ?? 0) + 1);
    while (count.size > 2) {
      const c = s[left++];
      count.set(c, count.get(c) - 1);
      if (count.get(c) === 0) count.delete(c);
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}
console.log(longestTwo("eceba"), longestTwo("ccaabbb"), longestTwo(""), longestTwo("aaaa"));
3 5 0 4

O(n) time: each character enters and leaves the window at most once.

3. Minimum brackets to add to make ( / ) valid.

Solution

With one kind of bracket a counter is enough. A ) with nothing open needs an added (; openers left at the end each need a ).

function minAdd(s) {
  let open = 0, add = 0;
  for (const c of s) {
    if (c === "(") open++;
    else if (open > 0) open--;
    else add++;
  }
  return add + open;
}
console.log(minAdd("())"), minAdd("((("), minAdd("()"), minAdd(")))((("));
1 3 0 6

Quick quiz

1. (From the video.) What does this print?

const stack = [];
console.log(stack.pop(), stack.length);

(A) TypeError (B) undefined 0 (C) null 0 (D) undefined -1

Answer

(B) undefined 0. pop on an empty array does not throw; it returns undefined and the length stays 0.

2. What does this print?

const s = "abc";
console.log(s[3], s[3] === s[2]);
console.log("x".repeat(3), "ab".repeat(0) === "");
Answer
undefined false
xxx true

Reading past the end of a string gives undefined, which is why i <= s.length closes the last run.

3. In the sliding window, why is left = Math.max(left, last.get(c) + 1) and not left = last.get(c) + 1?

Answer

last remembers positions from before the window started. If the earlier copy is already outside the window, last.get(c) + 1 is smaller than left and would move the window back over characters that repeat (abba → 3).

Interview questions

  1. Longest substring without repeating characters in O(n)? Sliding window with a Map of last positions; left = Math.max(left, last + 1).
  2. What is a sliding window? A range [left, right] over an array or string that grows on the right and shrinks on the left, so each element is processed a constant number of times.
  3. Substring vs subsequence? A substring is consecutive; a subsequence may skip characters (keeping order).
  4. What is run-length encoding? Writing each run of equal values as the value and its count: aabccc → a2b1c3.
  5. Why does a simple run loop lose the last run? It writes a run only when the character changes; the last run never sees a change.
  6. Check balanced brackets. A stack: push openers, pop on closers and compare, empty at the end. O(n).
  7. Why isn't a counter enough? It ignores the type and order of brackets (([)]).
  8. What is LIFO? Last in, first out: the stack's rule.
  9. What does [].pop() return? undefined.
  10. What if there is only one kind of bracket? A counter that never goes below zero and ends at zero is enough.

Glossary

Term Meaning Example
Substring Consecutive characters of a string "wke" in "pwwkew"
Subsequence Characters in order, gaps allowed "pwke" in "pwwkew"
Brute force Try every possibility every substring
O(n³) Time grows with the cube of the input 2× input → ~8× time
Set A collection of unique values new Set("aab").size → 2
Sliding window A [left, right] range that moves forward s.slice(left, right + 1)
left / right pointers Indexes of the window's ends right - left + 1 = length
Map of last positions Character → its latest index last.set(c, right)
Math.max The larger of its arguments Math.max(2, 1) → 2
String.fromCharCode Characters for codes String.fromCharCode(65) → "A"
repeat(n) A string repeated n times "ab".repeat(2) → "abab"
Run Consecutive equal characters ccc in aabccc
Run-length encoding Each run as character + count a2b1c3
Off-by-one error A loop that does one step too few or too many i < s.length loses the last run
s[s.length] Past the end: undefined "abc"[3]
Stack Add and remove only at the top an array with push/pop
LIFO Last in, first out the last box opened closes first
push / pop Add to / remove from the end of an array [1].pop() → 1
in operator Does the object have this key? ")" in pair → true
Short-circuit && The right side runs only if the left is truthy c in pair && stack.pop()
\D / \d+ A non-digit / one or more digits /(\D)(\d+)/g
Number(s) Turn text into a number Number("12") → 12
console.time / timeEnd Measure the time between two points brute: 1.936s

Summary

  • Longest substring without repeats: checking every substring is O(n³). A sliding window with a Map of last positions is O(n), and left must never move back (Math.max), or abba gives 3.
  • Compression: a counting Map loses positions; count runs by comparing with the previous character, and close the last run (i <= s.length). Return the original if the result isn't shorter, when asked.
  • Brackets: a counter forgets which bracket is open. A stack (push openers, pop and compare on closers, empty at the end) is O(n); only closing brackets should pop.

Next episode: Object questions I: deep clone (the JSON trap with Date and undefined, recursion, structuredClone), deep equality of two objects, and counting keys.