Low Complexity / TS 4.5+

valid_parentheses.ts

Solves LeetCode's Valid Parentheses entirely in the type system: characters are streamed off a template-literal string while a tuple acts as a stack, pushing openers and matching closers to decide VALID 👍 or INVALID 👎.

Edit the source on the left. As you type, the type checker re-evaluates and prints the fully-resolved value of each concrete type alias on the right.

TS 5.9

/* Valid Parentheses from leetcode: {@link https://leetcode.com/problems/valid-parentheses/} */ type Pop<T extends any[]> = T extends [...infer _, infer Tail] ? Tail : never; type Popped<T extends any[]> = T extends [...infer Head, infer _] ? Head : never; type Equal<Left extends any, Right extends any> = (<A>() => A extends Right ? true : false) extends <A>() => A extends Left ? true : false ? true : false; export type NotEqual<Left, Right> = true extends Equal<Left, Right> ? false : true; type Parentheses = { ")": "("; "]": "["; "}": "{"; }; type ValidParentheses< T extends string, P extends unknown[] = [] > = T extends `${infer Head}${infer Tail}` ? Head extends Parentheses[keyof Parentheses] ? ValidParentheses<Tail, [...P, Head]> : NotEqual<Pop<P>, Parentheses[Head & keyof Parentheses]> extends true ? "INVALID 👎" : ValidParentheses<Tail, Popped<P>> : P["length"] extends 0 ? "VALID 👍" : "INVALID 👎"; // ───────────────────────── @results ───────────────────────── type Test1 = ValidParentheses<"()[]{}">; //VALID type Test2 = ValidParentheses<"[{({[({(({{[{[[[]]]}]}}))})]})}]">; //VALID type Test3 = ValidParentheses<"[{({[({(({{[{[[[(]]]}]}}))})]})}]">; //INVALID

Compiler Output View

—