Katkat
Back

Decode a password string into letters

InstacartSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to parse and reconstruct a string based on specific numeric encoding rules, requiring careful index tracking and stack-based or recursive logic.

Problem Statement

You are given an encoded string that follows a specific pattern: digits represent the number of times a character (or sequence of characters) should be repeated, and delimiters are used to group sequences.

Rules:

  1. The encoding format is N[string], where the string inside the brackets is repeated N times.
  2. N can be a multi-digit integer (e.g., 12[a] becomes 'a' repeated 12 times).
  3. Encoded strings can be nested (e.g., 3[a2[b]] becomes 'abbabbabb').
  4. If no digits are present, the characters remain as they are.

Implement the function decode_string(s: str) -> str.

Constraints

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and brackets [].
  • The number of repetitions N is between 1 and 300.

Examples

Example 1: Input: s = "3[a]2[bc]" Output: "aaabcbc"

Example 2: Input: s = "3[a2[c]]" Output: "accaccacc"

Edge Cases

  • Empty strings or strings with no brackets.
  • Nested brackets with varying depths.
  • Multi-digit numbers as multipliers.

Hints

Hint 1

Consider using a stack to keep track of the current multiplier and the string segments processed so far.

Hint 2

When you encounter a closing bracket, pop the current string segment from the stack and multiply it by the integer retrieved from the multiplier stack.

Hint 3

A recursive approach can also solve this by identifying the substring between the matching opening and closing brackets.

Follow-up questions

  • How would your approach change if the input string contained invalid bracket structures (e.g., mismatched brackets)?
  • What is the time and space complexity of your solution in terms of the number of nested levels and the length of the output string?
  • Can you optimize the memory usage if the decoded string is expected to be extremely large?