Added solution for max length substring

anxious-coder-lhs · anxious-coder-lhs · commit 92007b3b19d3 · 2020-11-05T17:26:28.000+05:30
diff --git a/README.md b/README.md
@@ -52,7 +52,8 @@ Happy to accept any contributions to this in any langugage.
 17. [Leet Code 554 Brick Wall](https://leetcode.com/problems/brick-wall/) | [Solution 1](./level_medium/LeetCode_554_Brick_Wall_Medium.ts)
 18. [Leet Code 1190 Reverse Substrings Between Each Pair of Paranthesis](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/) | [Solution 1](level_medium/LeetCode_1190_Reverse_Substrings.ts) | [Solution Optimized](level_medium/LeetCode_1190_Reverse_Substrings_1.ts)
 19. [Leet Code 22 Generate Paranthesis](https://leetcode.com/problems/generate-parentheses/) | [Solution Brute Force](level_medium/LeetCode_22_Generate_Paranthesis_1.ts) | [Solution BF Optimized](level_medium/LeetCode_22_Generate_Paranthesis_2.ts)
-20. [Leet Code 54 Spiral Matrix] | [Solution](./med/../level_medium/SpiralMatrix.ts)
+20. [Leet Code 54 Spiral Matrix](https://leetcode.com/problems/spiral-matrix/) | [Solution](./med/../level_medium/SpiralMatrix.ts)
+21. [Leet Code 1239 - Maximum length of the unique character string](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/) | [Solution](./level_medium/LeetCode_1239_MaxLength.ts)
 
 
 ## Hard
diff --git a/level_medium/LeetCode_1239_MaxLength.ts b/level_medium/LeetCode_1239_MaxLength.ts
@@ -0,0 +1,39 @@
+/**
+ * Problem: Leet Code 1239
+ * Solution uses a backtracking approach to make all the possible combinations or sets of the input string.
+ * With that, we calculate that there are unique characters and should we backtrack. If not, the entire string
+ * is created recursively keeping track of the maximum length.
+ * 
+ * @param arr 
+ */
+function maxLength(arr: string[]): number {
+    return backTrackHelper("", arr, 0)
+};
+
+function backTrackHelper(str: string, arr: string[], idx: number): number {
+    
+    if (idx >= arr.length) {
+        return str.length;
+    }
+    
+    const newStr = str + arr[idx]
+    let maxLengthWithInclusion = 0;
+    if (isUnique(newStr)) {
+        maxLengthWithInclusion = backTrackHelper(newStr, arr, idx + 1);
+    }
+    
+    return Math.max(maxLengthWithInclusion, backTrackHelper(str, arr, idx + 1));
+}
+
+// Using the frequency counter for each character to see if we have any duplicates.
+function isUnique(str: string) {
+    
+    const chars: boolean[] = Array(26).fill(false);
+    for (let idx = 0; idx < str.length; idx++) {
+        const charCode = str.charCodeAt(idx) - 97;
+        if (chars[charCode] === true) return false;
+        chars[charCode] = true;
+    }
+    
+    return true;
+}
