/**
 * 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].
 * @see <a href="https://leetcode.com/problems/decode-string/">LeetCode</a>
 */
fun decodeString(s: String): String {
    var frequency = 0
    var currentString = mutableListOf<Char>()
    var currentNumber = mutableListOf<Char>()
    var stack = mutableListOf<Char>()
    s.forEach { char ->
        if (char == ']') {
            while (stack.last() != '[') {
                currentString.add(0, stack.removeLast())
            }
            stack.removeLast()
            while (stack.isNotEmpty() && stack.last().isDigit()) {
                currentNumber.add(0, stack.removeLast())
            }
            frequency = currentNumber.joinToString("").toInt()
            currentString.joinToString("").repeat(frequency).forEach { char -> stack.add(char) }
            currentString.clear()
            currentNumber.clear()
        } else {
            stack.add(char)
        }
    }
    return stack.joinToString("")
}

/**
 * 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].
 * @see <a href="https://leetcode.com/problems/decode-string/">LeetCode</a>
 */
fun decodeString(s: String): String {
    var frequency = 0
    var currentString = mutableListOf<Char>()
    var currentNumber = mutableListOf<Char>()
    var stack = mutableListOf<Char>()
    s.forEach { char ->
        if (char == ']') {
            while (stack.last() != '[') {
                currentString.add(0, stack.removeLast())
            }
            stack.removeLast()
            while (stack.isNotEmpty() && stack.last().isDigit()) {
                currentNumber.add(0, stack.removeLast())
            }
            frequency = currentNumber.joinToString("").toInt()
            currentString.joinToString("").repeat(frequency).forEach { char -> stack.add(char) }
            currentString.clear()
            currentNumber.clear()
        } else {
            stack.add(char)
        }
    }
    return stack.joinToString("")
}
