Decode String

MediumStackstack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an encoded string s and must return its decoded form. The encoding rule is k[encoded], which means the substring encoded should be repeated exactly k times. The integer k is always a positive integer, and the brackets are always well-formed and properly nested. The input may contain plain lowercase letters that are not wrapped in any brackets, and encoded segments may themselves contain nested encoded segments (for example, 3[a2[c]]). The repeat count k can have more than one digit (for example, 12[ab]), but it always appears immediately before an opening bracket. There are no whitespace characters in the input, and any digits that appear are only ever part of a repeat count k — never part of the literal text being decoded. Return the fully expanded string after applying every repetition.

Examples

Input: s = "3[a]2[bc]"
Output: "aaabcbc"
`3[a]` expands to `aaa` and `2[bc]` expands to `bcbc`, concatenated to give `aaabcbc`.
Input: s = "3[a2[c]]"
Output: "accaccacc"
The inner `2[c]` expands to `cc`, making the inner content `acc`. Repeating `acc` three times yields `accaccacc`.
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
`2[abc]` gives `abcabc`, `3[cd]` gives `cdcdcd`, and the trailing `ef` is appended unchanged.

Constraints

  • 1 <= s.length <= 30
  • `s` consists of lowercase English letters, digits, and the characters `[` and `]`.
  • `s` is guaranteed to be a valid, well-formed encoding.
  • All integers in `s` are in the range `[1, 300]`.
  • The length of the decoded output will not exceed 100000.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More stack problems