Generate N valid parentheses III

Problem Statement Get all valid permutations of l pairs of (), m pairs of <> and n pairs of {}, subject to the priority restriction: {} higher than <> higher than ().

Assumptions l, m, n >= 0 l + m + n >= 0

Examples l = 1, m = 1, n = 0, all the valid permutations are ["()<>", "<()>", "<>()"]. l = 2, m = 0, n = 1, all the valid permutations are [“()(){}”, “(){()}”, “(){}()”, “{()()}”, “{()}()”, “{}()()”].

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 (both of)

   No remaining capacity No remaining with low enough priority

2. complete with right brace

3. undo right brace

4. undo left brace

Key Takeaways Identical to previous solution expect lines 33-37 as we must check if a left branch is possible, i.e. count is valid and priority of incoming left brace is (strictly) less than the right brace on the stack. Plainly, we cannot insert a high priority left brace (incoming) into a nested low priority right brace (stack).

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 = {'(', '<', '{'};
  private final char[] rightBrace = {  ')', '>', '}'};

  public List<String> validParenthesesIII(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];

      int leftPrio = i; // just for readability
      int rightPrio = Integer.MAX_VALUE;
      if (!stack.isEmpty()) {
        rightPrio = getPrio(stack.peekFirst());
      }

      if (count[i] > 0 && isPrioLegal(leftPrio, rightPrio)){
        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);
    }
  }
  
  private int getPrio(char brace) {
    for (int i = 0; i < rightBrace.length; i++) {
      if (rightBrace[i] == brace) {
        return i;
      }
    }
    return -1;
  }
  
  private boolean isPrioLegal(int left, int right) {
    return left < right;
  }
}