Generate N valid parentheses II

Hard

Get all valid permutations of l pairs of (), m pairs of <> and n pairs of {}.

Assumptions

• l, m, n >= 0

• l + m + n > 0

Examples

l = 1, m = 1, n = 0, all the valid permutations are ["()<>", "(<>)", "<()>", "<>()"]

Solution: Recursive DFS 3 left branch one right branch

High Level:

Branch ( or < or { or complete

Base Case:

when no more braces to add && all braces are completed. Add to result

Recursive Rule:

1. Add left brace until no more to add

2. complete with right brace

3. undo right brace

4. undo left brace

public class Solution {
  private static final Map<Character, Character> braceMap;
  static {
      Map<Character, Character> tmpMap = new HashMap<>();
      tmpMap.put('{', '}');
      tmpMap.put('(', ')');
      tmpMap.put('<', '>');
      braceMap = Collections.unmodifiableMap(tmpMap);
  }

  private final char[] symbols = {'(', '<', '{'};
  public List<String> validParentheses(int l, int m, int n) {
    Deque<Character> stack = new ArrayDeque<>();
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    int[] count = {l, m , n};
    helper(count, stack, sb, result);
    return result;
    
  }

  private void helper(int[] count, Deque<Character> stack, StringBuilder sb, List<String> result){   
    if (count[0] + count[1] + count[2] + stack.size() == 0){
      result.add(sb.toString());
      return;
    }

    for (int i = 0; i < symbols.length; i++){
      char cur = symbols[i];
      if (count[i] > 0){
        sb.append(cur);
        count[i]--;
        stack.offerFirst(braceMap.get(cur));
        helper(count, stack, sb, result); //)
        stack.pollFirst();
        sb.deleteCharAt(sb.length() - 1);
        count[i]++;
      }
    }

    if (!stack.isEmpty()){
      char cur = stack.pollFirst();
      sb.append(cur);
      helper(count, stack,sb, result);
      stack.offerFirst(cur);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

Important note:

branching left first or right first does not matter. The key is to maintain a consistent state for each node by undoing previous add/remove push/pop.

Generic Solution:

public class Solution {
  public List<String> validParentheses(int l, int m, int n) {
    Map<Character, Integer> countMap = new HashMap<>();
    countMap.put('(', l);
    countMap.put('{', n);
    countMap.put('<', m);

    Map<Character, Character> braceMap = new HashMap<>();
    braceMap.put('{', '}');
    braceMap.put('(', ')');
    braceMap.put('<', '>');

    return genericValidParentheses(countMap, braceMap);
  }

  public List<String> genericValidParentheses(Map<Character, Integer> countMap, Map<Character, Character> braceMap) {
    Deque<Character> stack = new ArrayDeque<>();
    List<String> result = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    helper(countMap, braceMap, stack, sb, result);
    return result;
  }

  private void helper(Map<Character, Integer> countMap, Map<Character, Character> braceMap, Deque<Character> stack, StringBuilder sb, List<String> result) {
    int charsLeft = 0;
    for (int count : countMap.values()) {
      charsLeft += count;
    }

    if (charsLeft == 0 && stack.isEmpty()){
      result.add(sb.toString());
      return;
    }

    for (Character cur : countMap.keySet()) {
      if (countMap.get(cur) > 0){
        sb.append(cur);
        countMap.put(cur, countMap.get(cur) - 1);
        stack.offerFirst(braceMap.get(cur));
        helper(countMap, braceMap, stack, sb, result);
        stack.pollFirst();
        sb.deleteCharAt(sb.length() - 1);
        countMap.put(cur, countMap.get(cur) + 1);
      }
    }

    if (!stack.isEmpty()){
      char cur = stack.pollFirst();
      sb.append(cur);
      helper(countMap, braceMap, stack, sb, result);
      stack.offerFirst(cur);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}