Decode String

In this approach, we are going to loop through every character of input string s and store them into a Stack and whenever we encounter a clsing bracket ']' that means we have reached to the end of the characters which we need to decode using the integer before [, so we will construct a string using the characters from stack until we reach '[', for example if the input string is 2[abc], after adding characters a, b, and c to the stack, then when we see ], we will construct the string "abc".

Then, if the stack is not empty and the characters are digits 0-9, we construct the number before [ and repeat the string constructed before and put back the resultant string into stack, since the brackets could be nested.

import java.util.Stack;

public class DecodeString {

    static String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        for(char c: s.toCharArray()) {
            if( c != ']') {
                stack.push(String.valueOf(c));
            } else {
                String current ="";
                while (!"[".equals(stack.peek())) {
                    current = stack.pop() + current;
                }
                stack.pop(); // pop the '['

                // now we need to get the K number before that
                String k = "";
                while(!stack.isEmpty() && Character.isDigit(stack.peek().toCharArray()[0])) {
                    k = stack.pop() + k;
                }
                String decoded = current.repeat(Integer.parseInt(k));
                stack.push(decoded);
            }
        }
        return String.join("", stack);
    }

    public static void main(String[] args) {
        System.out.println(decodeString("2[abc]3[cd]ef"));
    }
}

Complexity Analysis:

Time complexity: Time complexity really depends on how big is the k, and how many of them are present in the input string. If there are n k's, the time complexity would be O (n * k)
Space complexity: O(n * k) for storing elements into stack.