Decode String Solution for Cognizant
Company: Cognizant · Difficulty: Medium · Topics: String, Stack
Problem Statement
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Examples
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Explanation: "3[a]" means "aaa", "2[bc]" means "bcbc".
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Explanation: "3[a2[c]]" means "3[acc]" which is "accaccacc".
Approach
Stack Approach (Optimal)
1. Use two stacks: one for numbers and one for strings
2. When we encounter a digit, build the number
3. When we encounter '[', push current string and number to stacks
4. When we encounter ']', pop and repeat the string
5. When we encounter a letter, append to current string
Time and Space Complexity
- Time Complexity: O(n) where n is the length of the output string
- Space Complexity: O(n) for the stack storage