1239. Maximum Length of a Concatenated String with Unique Characters

Hello, reader 👋🏽 ! Welcome to day 24 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1239. Maximum Length of a Concatenated String with Unique Characters.

🤔 Problem Statement

Given a list of strings arr, form a string s by the concatenation of subsequence of arr that has unique characters.
Return the maximum possible length of s.
E.g.:
- arr = ["un","iq","ue"] => maximum length = 4
  - Can form the following strings: "", "un", "iq", "ue", "uniq", "ique". The maximum length of all these possible strings are 4.
- arr = ["abcdefghijklmnopqrstuvwxyz"] => maximum length = 26
- arr = ["aa", "bb"] => maximum length = 0.
  - Cannot form a string since no element has unique characters.

💬 Initial Thought Process

The question can be looked at as forming subsets of an array and calculating the combined length of all subsets that have unique characters.
Hence, this can be broken down into a recursive solution with two choices at every level of the tree: selecting or not selecting an element at an index.
But selecting an element at every index should also depend on whether:
1. This element contains unique characters
2. Combining this element with the previous subset produces a string with all unique characters.
If bot the above are true, then only we can add the current subsequence to the string to be formed.

💬 Thought Process - Backtracking using seen array/ set

At every recursion call we will pass a seen array/ set and mark the characters of all subsets seen so far.
If the current element has characters that have already been marked as seen in the array/ set, then we will not include this in the string to be formed.
Or if the current element has repeated characters, we don't consider this element.
We continue doing this and find the max length of strings formed by either selecting or not selecting the element.

👩🏽‍💻 Solution - Backtracking using seen array/ set

Below is the code for the backtracking approach using set.

class Solution {
  public int maxLength(List<String> arr) {
      if(arr == null || arr.size() == 0) {
          return 0;
      }
      return maxLengthHelper(arr, 0, new int[26]);
  }

  private int maxLengthHelper(List<String> arr, int index, int[] seen) {
      if(index == arr.size()) {
          return 0;
      }

      // O(1) since the length is only 26
      int[] currSeen = seen.clone();
      String sequence = arr.get(index);
      boolean hasUnique = hasUniqueChars(sequence, currSeen);

      int includeCurr = 0;
      if(hasUnique) {
         includeCurr =  sequence.length() +  maxLengthHelper(arr, index+1, currSeen);
      }

      int excludeCurr = 0 + maxLengthHelper(arr, index+1, seen);

      return Math.max(includeCurr, excludeCurr);
  }

  private boolean hasUniqueChars(String sequence, int[] seen) {
      for(char ch: sequence.toCharArray()) {
          if(seen[ch - 'a'] == 1) {
              return false;
          }
          else {
              seen[ch - 'a']+=1;
          }
      }

      return true;
  }
}

Time Complexity: O(2^n * m)
  - n = number of elements in the list
  - m = length of string
      - The maximum depth of the tree is n and at every level there are two branches.
      - We are also traversing the string at index i in all the levels
Space Complexity: O(n * m)
  - n = number of elements
  - m = max length of string
      - n for implicit stack space and m space for the string at every index i

💬 Thought Process - Backtracking using string

We can also recursively form strings by selecting subsequences from the array.
Let's look at the code for the same.

👩🏽‍💻 Solution - Backtracking using string

The code for the backtracking approach using string is below.

class Solution {
  public int maxLength(List<String> arr) {
      if(arr == null || arr.size() == 0){
          return 0;
      }

      return maxLengthHelper(arr, 0, new StringBuilder(""));
  }

  private int maxLengthHelper(List<String> arr, int index, StringBuilder sb) {
      if(index == arr.size()) {
          return sb.length();
      }

      String subsequence = arr.get(index);

      // If we can combine the current subsequence with the previous string
      boolean hasUniqueChars = hasUnique(sb.toString() + subsequence);

      int includeCurr = 0;
      if(hasUniqueChars) {
          includeCurr =  maxLengthHelper(arr, index+1, sb.append(subsequence));

          int n = sb.length();
          int m = subsequence.length();
          sb = sb.delete(n-m, n);
      }

      int excludeCurr = maxLengthHelper(arr, index+1, sb);

      return Math.max(includeCurr, excludeCurr);
  }

  private boolean hasUnique(String s) {
      int[] seen = new int[26];
      for(int j = 0; j < s.length(); j++) {
          char c = s.charAt(j);
          if(seen[c - 'a'] == 1) {
              return false;
          }
          seen[c - 'a']++;
      }

      return true;
  }
}

Time Complexity: O(2^n * m)
  - n = number of elements
  - m = max length of string formed
      - There are 2 branches at every level and the tree has a total of n levels.
      - We are passing the string m that is formed to every call
Space Complexity: O(n * m)
  - n = number of elements
  - m = max length of string
      - n for implicit stack space and m for the string formed that is passed to every call

You can find the code for this question in the GitHub repo here: 1239. Maximum Length of a Concatenated String with Unique Characters.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!