decodeString.go

/*
Challenge: decodeString
https://codefights.com/interview-practice/task/dYCH8sdnxGf5aGkez/description

Given an encoded string, return its corresponding decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is repeated exactly k times. Note: k is guaranteed to be a positive integer.

Note that your solution should have linear complexity because this is what you will be asked during an interview.

Example

For s = "4[ab]", the output should be

decodeString(s) = "abababab";

For s = "2[b3[a]]", the output should be

decodeString(s) = "baaabaaa";

For s = "z1[y]zzz2[abc]", the output should be

decodeString(s) = "zyzzzabcabc".

Input/Output

[time limit] 4000ms (go)
[input] string s

A string encoded as described above. It is guaranteed that:

the string consists only of digits, square brackets and lowercase English letters;
the square brackets form a regular bracket sequence;
all digits that appear in the string represent the number of times the content in the brackets that follow them repeats, i.e. k in the description above;
there are at most 20 pairs of square brackets in the given string.
Guaranteed constraints:

0 ≤ s.length ≤ 80.

[output] string
*/
func decodeString(s string) string {
        
    if len(s) == 0 {
        return ""
    }
    
    // start reading
    // if chars add to result
    // if num repeat sub result x times
    // recurse remaining
    
    // start reading right to left
    res := ""
    for z, r := range s {
        if r >= 97 && r < 123 {
            res = res + string(r)
        } else if r >= 48 && r <= 57 {
            // read until we hit bracket
            numStr := ""
            i := z
            r = rune(s[i])
            for  r != '[' {
                numStr += string(s[i])
                i++
                r = rune(s[i])
            }
            num, _ := strconv.Atoi(numStr)

            // find closing bracket
            closeIndex := 0
            lcount := 0
            for n, r := range s[i:] {
                if r == '[' {
                    lcount++
                } else if r == ']' {
                    lcount--
                }
                if lcount == 0 {
                    closeIndex = i + n
                    break
                }
            }
            recurseString := decodeString(s[i+1:closeIndex])
           
            // append the result x times
            for j := 0; j < num; j++ {
                res = res + recurseString
            }
           
            // recurse on anything right of the closing bracket
            res = res + decodeString(s[closeIndex+1:])
            break
        }     
    }
    return res
}