Decode String (Interview Solution)

How to Solve Decode String

Decode String Introduction

Decode String is a problem where a string of numbers and letters need to be decoded to reveal a hidden message. This is a common, albeit simplified, problem in cryptography, involving a multi-step approach and the application of recursion and additional data structures to improve time complexity.

Decode String Problem

Part 1 - Decode String Simplified

The simplified version of "decode string" presents us with an alpha-numeric string where a number may come before any letter. Given such a string, decode the string so that each number/letter combinations is expanded.

Example 1

input: 4a
output: aaaa

Example 2

input: a2b10c
output: abbcccccccccc

Part 2 - Decode String (Standard Version)

Given an encoded string s, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note that k is guaranteed to be a positive integer.

Constraints

Example 1

input: abcdefg
output: abcdefg

Example 2

input: ab2[c]3[de4[f]]
output: abccdeffffdeffffdeffff

Example 3

input: 2[2[2[a]]]
output: aaaaaaaa

Decode String Solutions

There are two problems we will need to solve to successfully expand our string:

  1. Parsing - We need to be able to walk through our input string and extract the counts and groupings.
  2. Groups within groups - We need a way of tracking the nested structure of our encoded string.

The second issue is certainly related to parsing, but we will pull in some additional tools to manage it.

We will start with the simplified problem as a warmup exercise. This will give us a chance to get a feel for how parsing works. Once we have that under our belt we will move on to the more complex Leetcode version.

Approach to Simplified Problem

As a reminder, in this case, we have an alpha-numeric string where an integer may come before any alpha character. To solve this problem we will walk through our string one character at a time. We will use a string variable called count to store any digit information we encounter. We are using a string because we may need to store multiple digits and concatenating strings is trivial. Now each time we encounter an alpha character we can look at the count to determine the number of times that character should appear. After adding an alpha character, count will be reset.

In the python solution, we are using a bit of cleverness when it comes to multiplying count by char. Multiplying an integer N by a string S duplicates the string N times. In the javascript solution, we need to create a helper function to determine if a character is a digit.

Decode String Python, JavaScript and Java Solutions - Simplified Version

def decode_string(s: str) -> str:
  solution_str = ""

# using a string to make our lives easier
  count = ""

for char in s:
    if char.isDigit():
      count += char
    else:
      if count == "":
        solution_str += char
      else:
        # multiplying a string by an int creates copies of the string!
        solution_str += int(count) * char
        count = ""

return solution_str

Time/Space Complexity

Approach to Decode String - Standard Version (Recursion)

Now that we've warmed up using the simpler problem, let's tackle the more difficult problem!

In this more complex version our input string is different in two ways:

  1. Now instead of using numbers to expand out a single character, a group of characters may be expanded out. Groups are defined by square brackets []. For instance 3[ab] would expand out to ababab. Note, any time there is a number, it is guaranteed to be followed by [].
  2. We are allowed to have groups inside of groups.

Similar to the previous solution we need to walk through our input string and categorize each character. Because we may have groups within groups, as we walk through our string we need a way of tracking which group we are currently parsing. We will introduce a new variable called depth to track this. When we first start parsing the string, depth will be 0. Each time we step into a new group (when we encounter a [) depth will go up by one, and depth will go down by one each time we step out of a group (when we encounter a ]). When depth returns to 0 we will know that we have processed an entire group.

Decode String Python, JavaScript and Java Solutions - Standard Version (Recursion)

def decode_string(s: str) -> str:
  return_string = ""
  count = ""
  contents = ""
  depth = 0

for char in s:
    if depth == 0:
      if char.isdigit():
        count += char
      elif char == "[":
        depth += 1
      else:
        return_string += char
    else:
      if char == "]":
        depth -= 1

if depth == 0:
          # we found the end of a grouping
          # expand it and add it to our output string.
          return_string += int(count) * self.decode_string(contents)
          count = ""
          contents = ""
        else:
          contents += char
      else:
        if char == "[":
          depth += 1
        contents += char

return return_string

Time/Space Complexity

Approach to Decode String - Standard Version (Stacks)

Now, our recursive solution has the weakness of needing to parse subgroups multiple times. For instance take the string 4[3[abc]3[xyz]]. Our parser would walk over the entire string, then over 3[abc]3[xyz], then [abc], and finally over [xyz]. This unnecessarily increases our time complexity!

In this approach, we are going to work on shaving some time off by processing groups as we parse. To do this we are going to create a stack. Each element of the stack represents a group. We will add elements to the stack as we encounter subgroups. Each time we finish parsing a group (encounter a ]) we will pop it off the stack, expand it out, and add it to the new top element on the stack. Once all groups have been processed we will have only a single group in our stack. This is our final solution!

Decode String Python, JavaScript and Java Solutions - Standard Version (Stacks)

class Encoding:
    def __init__(self, count:str = "", contents:str = "") -> None:
        self.count = count
        self.contents = contents

def decode_string(s: str) -> str:
    encoding_stack = [Encoding()]
    count = ""

for char in s:
        if char.isdigit():
            count += char
        elif char == "[":
            encoding_stack.append(Encoding(count=count, contents=""))
            count = ""
        elif char == "]":
            encoding = encoding_stack.pop()
            expanded_encoding = int(encoding.count) * encoding.contents
            encoding_stack[-1].contents += expanded_encoding
        else:
            encoding_stack[-1].contents += char

return encoding_stack[0].contents

Time/Space Complexity