We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decode String

Number: 394

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Amazon, Meta, Zoho, Microsoft, TikTok, Apple, Oracle, Salesforce, Nutanix, Wix, Huawei, Splunk, Goldman Sachs, Activision, Tinkoff, Cisco, eBay, Walmart Labs, Uber, Roku, Adobe, Yahoo, Sumo Logic, Snowflake, Coupang, Yelp

Problem Description

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. All numbers represent the repeat count and the input is always valid.

Key Insights

  • Use a stack or recursion to manage nested encoded patterns.
  • Process the string character by character, accumulating digits for the repeat count.
  • When encountering a '[', start a new context (recursively or via a new stack frame) for the encoded substring.
  • When encountering a ']', finish the current context and repeat the accumulated substring as needed.
  • Careful handling of multi-digit numbers is essential.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), for the recursion stack or the auxiliary stack used.

Solution

We can solve this problem using a recursive approach. When we see a digit, we determine the full repeat count. Upon encountering a '[', we recursively read the encoded substring until the corresponding ']'. Each recursive call returns the decoded substring until it hits a ']', which is then repeated based on the previously computed count.

Alternatively, an iterative solution using a stack is also feasible. As we parse the string, push the current string and number onto the stack when encountering '[', then pop and combine when ']' is reached. This approach correctly handles nested patterns.

Code Solutions

def decodeString(s: str) -> str:
    # index pointer as a list so it can be mutable within recursion
    def helper(i: int) -> (str, int):
        decoded = ""
        while i < len(s):
            if s[i].isdigit():
                # build the number (it might be more than one digit)
                k = 0
                while i < len(s) and s[i].isdigit():
                    k = k * 10 + int(s[i])
                    i += 1
                # skip the '[' character
                i += 1  # skip '['
                # recursively solve the substring inside the brackets
                sub, i = helper(i)
                # append the substring repeated k times
                decoded += sub * k
            elif s[i] == ']':
                # returning decoded string and new index after ']'
                return decoded, i + 1
            else:
                # accumulate alphabetic characters directly
                decoded += s[i]
                i += 1
        return decoded, i

    result, _ = helper(0)
    return result

# Example usage
#print(decodeString("3[a2[c]]"))  # Output: "accaccacc"
← Back to All Questions