How to Decode a String?

Decoding a string is a common problem in programming interviews. It often involves transforming a given input string into another format, typically based on rules for compression or encoding. This task is not only a test of coding skills but also a chance to demonstrate problem-solving capabilities.

Understanding the Problem

Often, the string decoding problem involves patterns where numbers define how many times each character or sequence of characters should be repeated. A typical example is the string "3[a2[c]]", which decodes to "accaccacc". Understanding how to break down the string into manageable parts and apply the decoding rules is key.

Example Interview Questions

Question 1: Decode the String

Question: Given a string encoded in the form k[encoded_string], decode it to get the original string. The encoded_string is guaranteed to be a valid string.

Example Input:

1s = "2[abc]3[cd]ef"

Expected Output:

1abcabccdcdcdef

How to Answer

To decode a string like this, a stack can be used to manage the parts of the string. Here's how to approach writing a function in Python:

1def decode_string(s: str) -> str:
2    stack = []
3    current_num = 0
4    current_string = ""
5    
6    for char in s:
7        if char.isdigit():
8            current_num = current_num * 10 + int(char)
9        elif char == '[':
10            stack.append(current_string)
11            stack.append(current_num)
12            current_string = ""
13            current_num = 0
14        elif char == ']':
15            num = stack.pop()  # Number before '['
16            prev_string = stack.pop()  # String before '['
17            current_string = prev_string + current_string * num
18        else:
19            current_string += char
20
21    return current_string
22
23# Test the function
24print(decode_string("2[abc]3[cd]ef"))  # Output: "abcabccdcdcdef"

Explanation of the Code

1. Initialization: A stack is created to hold numbers and strings.
2. Loop through each character:
   • If the character is a digit, it builds the current_num.
   • If it's an opening bracket [, it pushes the current string and number onto the stack.
   • If it's a closing bracket ], it pops from the stack to get the number and the previous string, then builds the current_string accordingly.
   • If it’s a letter, it simply appends it to current_string.
3. Final return: At the end of the loop, current_string holds the decoded result.

Question 2: Advanced Decoding with Nested Structures

Question: Can you decode a more complex nested string like "3[a2[b3[c]]]"?

Expected Output:

1abccbccabccbccabccbcc

How to Answer

The same approach applies, as it requires handling nested structures with a stack. Below is the implementation:

1def decode_string(s: str) -> str:
2    stack = []
3    current_num = 0
4    current_string = ""
5    
6    for char in s:
7        if char.isdigit():
8            current_num = current_num * 10 + int(char)
9        elif char == '[':
10            stack.append(current_string)
11            stack.append(current_num)
12            current_string = ""
13            current_num = 0
14        elif char == ']':
15            num = stack.pop()
16            prev_string = stack.pop()
17            current_string = prev_string + current_string * num
18        else:
19            current_string += char
20
21    return current_string
22
23# Test the function with advanced case
24print(decode_string("3[a2[b3[c]]]"))  # Output: "abccbccabccbccabccbcc"

• The most common technique to decode strings is using a stack.
• Keep track of numbers and substrings to handle nested structures.
• The implementation can handle various levels of complexity in the encoded string.

By familiarizing oneself with these concepts, candidates can confidently tackle string decoding problems in interviews. Crafting test cases and understanding variations are also beneficial for demonstrating problem-solving skills effectively in this topic.