Start learning free

LESSON 301 OF 348 · STACK

Decode String in Kotlin: A Stack of Counts and Buffers

Practice O(n) Read the full explanation

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. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.


Example 1:

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

Example 2:

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

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

STEP 1 OF 16
    Ctrl + Enter to check

    KOTLIN · STACK

    Decode String in Kotlin, explained

    Problem overview

    The function decodeString receives an encoded string and returns the decoded one. The rule is k[encoded_string]: the text inside the square brackets is repeated exactly k times. Groups can nest, can sit next to plain letters, and the input is always valid. Digits appear only as repeat counts, so inputs like 3a or 2[4] never occur. A count can have several digits, up to 300, and s has at most 30 characters.

    For "3[a2[c]]" the inner group 2[c] becomes cc, so the outer group is 3[acc], which is "accaccacc". For "2[abc]3[cd]ef" there are two groups and a plain tail, giving "abcabccdcdcdef".

    Approach: decode the innermost group first

    Nesting means the group that closes first is the one that opened last, which is the shape of a stack. The idea is to scan once from left to right and keep two kinds of entries on one stack of strings: a count, stored as a string of digits, and a text buffer for the characters collected since a [ opened.

    When a ] arrives, the top entry is the finished text and the entry under it is its count. Pop both, repeat the text, and give it to whatever is now on top: if that is the buffer of an enclosing group, the decoded text is appended to it, and if the stack is empty, it becomes the first buffer of the result.

    Here is "3[a2[c]]", writing each stack from bottom to top:

    3       ["3"]
[       ["3", ""]
a       ["3", "a"]
2       ["3", "a", "2"]
[       ["3", "a", "2", ""]
c       ["3", "a", "2", "c"]
]       ["3", "acc"]
]       ["accaccacc"]

    Each ] removes the two top entries and puts back one, so the stack shrinks by one entry per group. At the end a single entry is left: the decoded string.

    Step by step

    1. Create the stack as an empty mutable list of strings. Counts and text share it, so every entry is a string.
    2. Loop over the characters of s as c. Each character is a bracket, a letter or a digit, and each kind is handled separately.
    3. Handle [. Push an empty string. It will collect the text of this group.
    4. Handle letters. A letter belongs to the text, never to a count.
    5. Make sure there is a buffer. A letter can appear before any bracket, as in the ef tail of the third example, when the stack may be empty. In that case push an empty buffer first, then append the letter to the last entry.
    6. Handle digits. They build a count, which must stay apart from the decoded text.
    7. Peek at the top. Read the last entry, or an empty string when the stack is empty, into top.
    8. Start a new count when top isn't made only of digits: push the digit as its own entry. A count is beginning, not continuing.
    9. Continue the count otherwise: the top is already a number being built, so the digit is appended to it. This is how 12 stays in one entry.
    10. Handle the final case, ]. Anything that isn't [, a letter or a digit must be a closing bracket.
    11. Pop the text into currStr. It was pushed last, so it comes off first.
    12. Pop the count into currNum and convert it to an Int.
    13. Repeat the text currNum times.
    14. Place the result. If the stack is now empty, push the repeated text as a new buffer. Otherwise append it to the last entry, which is the enclosing group's buffer.
    15. Return the last entry. For a valid input exactly one buffer remains and it holds the whole answer.

    The solution in Kotlin

    class Solution {
    fun decodeString(s: String): String {
        val stack = mutableListOf<String>()
        for (c in s) {
            if (c == '[') {
                stack.add("")
            } else if (c.isLetter()) {
                if (stack.isEmpty()) {
                    stack.add("")
                }
                stack[stack.size - 1] += c
            } else if (c.isDigit()) {
                val top = if (stack.isEmpty()) "" else stack[stack.size - 1]
                if (!top.matches(Regex("\\d+"))) {
                    stack.add(c.toString())
                } else {
                    stack[stack.size - 1] += c
                }
            } else {
                val currStr = stack.removeAt(stack.size - 1)
                val currNum = stack.removeAt(stack.size - 1).toInt()
                val repeated = currStr.repeat(currNum)
                if (stack.isEmpty()) {
                    stack.add(repeated)
                } else {
                    stack[stack.size - 1] += repeated
                }
            }
        }
        return stack[stack.size - 1]
    }
}

    The Kotlin details worth knowing:

    • += on a list element. Strings are immutable, so stack[stack.size - 1] += c builds a new string and stores it back into that slot. It works because the list is a MutableList. The right side can be a Char, since String + Char appends the character.
    • val and a mutable list. val stack stops the name from being reassigned. The list itself still grows and shrinks.
    • The regular expression. "\\d+" is the pattern \d+, one or more digits, written with the backslash doubled in a Kotlin string. matches needs the whole string to fit the pattern, so an empty string, which is what top holds for an empty stack, does not match. A buffer like "a" does not match either, while "12" does.
    • isLetter() and isDigit() are methods on Char, so the character classes need no manual range checks.
    • if as an expression. val top = if (stack.isEmpty()) "" else stack[stack.size - 1] picks a value, as Kotlin has no ternary operator.
    • removeAt returns the removed element. That is why each pop can be assigned to a name in the same line.
    • toInt() and repeat(). "12".toInt() is the number 12, and "ab".repeat(3) is "ababab".
    • The final else. It runs for every character not handled earlier. With valid input that can only be ].

    Complexity

    Let L be the length of the decoded output, which the problem keeps at or below 100,000.

    Time: about O(L * d), where d is the nesting depth. Every character that ends up in the output is produced by repeat and then copied into each enclosing buffer by the concatenations on the way out. With 30 input characters the depth is small, so this is effectively linear in the output size.

    Space: O(L). The stack holds the partly decoded buffers and counts, and the largest of them is no longer than the final output.

    Edge cases and common mistakes

    • No brackets. "abc" pushes one buffer on the first letter and returns it unchanged.
    • Multi-digit counts. "10[a]" gives ten as. Treating each digit as a separate count would break it, which is why a digit is appended to the top entry while that entry is all digits.
    • Letters after a group. "ab2[c]" gives "abcc". The plain ab sits below the count, and the decoded group is appended to it.
    • Text between groups. "2[a]b3[c]" gives "aabccc". After the first group the stack holds aa, and b is appended to it before the next count arrives.
    • Deep nesting. "2[2[2[a]]]" gives eight as.
    • Using c == "[". A Char and a String can't be compared with == in Kotlin; the code does not compile. Use single quotes for characters.
    • Forgetting to fold the group back. If the repeated text is pushed as a new entry when the stack isn't empty, the enclosing group never receives it and the final stack has extra entries.

    Testing

    • "3[a]2[bc]" gives "aaabcbc".
    • "3[a2[c]]" gives "accaccacc".
    • "2[abc]3[cd]ef" gives "abcabccdcdcdef".
    • "10[a]" gives "aaaaaaaaaa".
    • "2[a]b3[c]" gives "aabccc".
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free