Decode String
Medium About 20 min Free, no account needed
Expand k[encoded] patterns, nesting included.
The brief
Given an encoded string where k[inner] means "repeat inner k times",
return the decoded string. Patterns nest: 3[a2[c]] decodes to
"accaccacc". Counts may have several digits (10[a]).
A single-level scanner that pairs the first [ with the first ] mangles
nested patterns, and reading one digit at a time breaks 10[a]. Keep a
stack of (prefix, repeat-count) frames, push at [, pop and multiply at
].
Starter code
using System;
public class Solution
{
// TODO: return the string with all k[inner] patterns decoded.
public string DecodeString(string s)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Stacks
- Use last-in, first-out state for nesting, matching and expression evaluation.
- String processing
- Parse, scan and match text character by character with correct edge cases.
Related katas
- Simplify Unix Path Medium Free Canonicalize a Unix path - and survive the .. that climbs past root.
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Evaluate Reverse Polish Notation Medium Free Evaluate a postfix expression - and get integer division right.
- Count Substring Occurrences Medium Free Count overlapping occurrences by comparing characters, not slicing strings.