Parsing and Validating Strings

String problems in frontend work are rarely "reverse this string" — they're parsing and validating structured text a user typed, or that your own code generates: a template string with placeholders, a color code, a balanced set of brackets in something a code editor is checking live. This lesson treats those as the algorithms they actually are.

Balanced brackets: the canonical stack problem

A code editor highlighting mismatched brackets needs to answer: is this string's brackets balanced?

function isBalanced(str) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };
 
  for (const char of str) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    } else if (char === ")" || char === "]" || char === "}") {
      if (stack.pop() !== pairs[char]) return false; // wrong bracket, or nothing to close
    }
  }
 
  return stack.length === 0; // anything left unclosed means it's not balanced
}

Why a stack and not a simple open-count versus close-count comparison? Because balance requires two separate things to be true: equal counts, and correct nesting order. "([)]" has one of each bracket type, perfectly equal counts — and is still unbalanced, because the ) closes before the [ that opened after it. A stack captures exactly the ordering information a counter throws away: at any point, the top of the stack is the specific opener that must close next, and popping checks that the current closer matches it.

Time complexity: one pass over the string, O(n). Space: the stack holds every unmatched opener simultaneously in the worst case — a string like "(((((" pushes all n characters before a single pop — so O(n) auxiliary space in the worst case, even though many real inputs use far less.

Tokenizing a template string in one pass

Template engines, i18n string interpolation, and simple markup all need to split a string into literal text and placeholders:

function tokenize(template) {
  const tokens = [];
  let literal = "";
 
  for (let i = 0; i < template.length; i++) {
    if (template[i] === "{") {
      if (literal) { tokens.push({ type: "literal", value: literal }); literal = ""; }
      const end = template.indexOf("}", i);
      tokens.push({ type: "placeholder", value: template.slice(i + 1, end) });
      i = end; // jump past the closing brace
    } else {
      literal += template[i];
    }
  }
  if (literal) tokens.push({ type: "literal", value: literal });
 
  return tokens;
}
 
tokenize("Hello {name}, you have {count} items");
// [{type:"literal",value:"Hello "}, {type:"placeholder",value:"name"},
//  {type:"literal",value:", you have "}, {type:"placeholder",value:"count"},
//  {type:"literal",value:" items"}]

This is a single left-to-right scan: the index i only ever moves forward (even the jump via template.indexOf("}", i) still lands further ahead, never back), and each character contributes to exactly one token. That's O(n) time for a string of length n — genuinely one pass, not "one pass per placeholder," which is the trap a less careful version (re-scanning from the start after each match) would fall into.

Why a validation regex is a state machine in disguise

A common frontend task — "does this look like a valid hex color," "is this a plausible-looking email" — usually gets solved with a regular expression, and that's often the right call. But it's worth seeing why it works: a regex engine matching a pattern like /^#[0-9a-f]{6}$/i is walking the string character by character, maintaining an internal notion of "which part of the pattern could I still be matching" — which is exactly a state machine, just one you didn't have to hand-write.

function isValidHexColor(str) {
  return /^#[0-9a-f]{6}$/i.test(str);
}

That's O(n) for a pattern like this one, because it has no ambiguity about how to consume characters — each character either matches the expected position or the whole thing fails immediately. The genuine danger zone is different: patterns with nested quantifiers over overlapping character classes (the classic example is something shaped like /^(a+)+$/ against a long non-matching string) can force the engine to backtrack through exponentially many ways of re-grouping the same repeated matches — a real, documented failure mode called catastrophic backtracking, not a theoretical one. Simple, well-anchored patterns like the hex-color check above don't have this problem; it's specifically nested repetition that does.

What to remember

• Balance and matching problems need a stack, not a count — a stack captures ordering ("what needs to close next"), which a plain count of opens/closes cannot.
• A well-written scanner processes structured text in one linear pass by always moving forward, giving O(n) time even when it's splitting the input into multiple pieces.
• A validation regex is a state machine the engine runs for you — genuinely O(n) for simple, well-anchored patterns, but nested quantifiers over overlapping character classes can trigger real, exponential-time backtracking on adversarial input.
• When a format's rules get complex enough that a regex becomes unreadable or risks pathological backtracking, a small hand-written scanner with explicit state is usually the more maintainable and more predictable choice.