> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dfs-permutations/generate-n-valid-parentheses-3.md).

# 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**\
&#x20;   l, m, n >= 0\
&#x20;   l + m + n >= 0

**Examples**\
&#x20;   l = 1, m = 1, n = 0, all the valid permutations are \["()<>", "<()>", "<>()"].\
&#x20;   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).

```java
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;
  }
}

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dfs-permutations/generate-n-valid-parentheses-3.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.