ValidString

https://leetcode.com/discuss/interview-question/1557009/amazon-online-coding-assessment-sde-2

• There are 3 rules for a valid string:

  1. An empty string is valid

  2. You can add same character to a valid string X, and create another valid string yXy

  3. You can concatenate two valid strings X and Y, so XY will also be valid.

  4. Ex: vv, xbbx, bbccdd, xyffyxdd are all valid.. (It's essentially the valid parentheses question but with alphabets instead of parentheses https://leetcode.com/problems/valid-parentheses/. This can be solve in O(n) with a stack.)

     Using stack - https://leetcode.com/playground/MYxTQJdX

     static boolean isValid(String s) {
             Stack<Character> st =  new Stack<>();
             for(char c : s.toCharArray()){
                 if(st.isEmpty()){
                     st.push(c);
                 }else if(st.peek() == c){
                     st.pop();
                 }else{
                     st.push(c);
                 }
             }
             return st.isEmpty();
         }