Added LC solutions for 351 and 1573

anxious-coder-lhs · anxious-coder-lhs · commit 07faa294f5b0 · 2020-11-24T01:03:21.000+05:30
diff --git a/README.md b/README.md
@@ -60,6 +60,8 @@ Happy to accept any contributions to this in any langugage.
 25. [Leet Code 1647 - Minimum Deletions to Make Character Frequency Unique](https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/) | [Solution](level_medium/LeetCode_1647_Min_Deletions_For_Unique_Freq.ts)
 26. [Microsoft OA - Max Sum of Numbers with Equal Sum Digits](https://leetcode.com/discuss/interview-question/915683/) | [Solution](./level_medium/MaxSumOfNumbersWithEqualSumOfDigit.ts)
 27. [Microsoft OA - Min Moves to Make String without 3 Identical Chars](https://molchevskyi.medium.com/microsoft-interview-tasks-min-moves-to-make-string-without-3-identical-consecutive-letters-abe61ed51a10) | [Solution](./level_medium/MinMovesToMakeStringWithout3IdenticalChars.ts)
+28. [Android Unlock Patterns](https://leetcode.com/problems/android-unlock-patterns/) | [Solution 1](./level_medium/LeetCode_351_Android_Unlock.ts) | [Solution 2](/level_medium/LeetCode_351_Android_Unlock_1.ts)
+29. [Leet Code 1573 - Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/) | [Solution 1](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String_1.ts) | [Solution](./level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String.ts)
 
 
 ## Hard
diff --git a/level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String.ts b/level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String.ts
@@ -0,0 +1,28 @@
+function numWays(s: string): number {
+    let ways = 0;
+    for (let pivot1 = 1; pivot1 <= s.length - 2; pivot1++) {
+        for (let pivot2 = pivot1 + 1; pivot2 <= s.length - 1; pivot2++) {
+            const bounds1 = [0, pivot1 - 1]
+            const bounds2 = [pivot1, pivot2 - 1]
+            const bounds3 = [pivot2, s.length - 1]
+            if (haveEqualOnes(s, bounds1, bounds2, bounds3)) ways++
+        }
+    }
+    
+    return ways;
+};
+
+function haveEqualOnes(s: string, str1: number[], str2: number[], str3: number[]) {
+    const countStr1 = countOnes(s, str1)
+    const countStr2 = countOnes(s, str2)
+    const countStr3 = countOnes(s, str3)
+    return countStr1 === countStr2 && countStr2 === countStr3
+}
+
+function countOnes(s: string, bounds: number[]) {
+    let count = 0;
+    for (let idx = bounds[0]; idx <= bounds[1]; idx++) {
+        if (s[idx] === '1') count++
+    }
+    return count
+}
diff --git a/level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String_1.ts b/level_medium/LeetCode_1573_Number_Of_Ways_To_Split_String_1.ts
@@ -0,0 +1,44 @@
+/**
+ * Leet Code 1573
+ * 
+ * Solution is essentially a combination problem. The string can be divied into 3 sections with the help of 2 pointers/cuts.
+ * Each cut can only be created such that the number of 1s are equal, so essentially at a min requiring the needed 1s, while
+ * at maximum requiring the needed 1s. This creates a combinatory choice of choosing the cut point. For each possible
+ * cut point in 1st, we can choose a cut point in 2nd.
+ * 
+ * Time: O(n) since the scan is required only linearly.
+ * Space: O(1) since no other space is needed.
+ *  
+ * @param s 
+ */
+function numWays(s: string): number {
+    const onesCount = countOnes(s);
+    const mod = 10 ** 9 + 7;
+
+    // If the equal partition cannot be made.
+    if (onesCount % 3 !== 0) return 0;
+
+    // If the counts are 0, we have to make combinations for the central array, assuming 0 and 0 at ends.
+    // So, we have 1 + 2 + 3 + .............. + (n-1) + (n-2), leading the sum range.
+    if (onesCount === 0) {
+        return ((s.length - 2) * (s.length - 1) / 2) % mod;
+    }
+    
+    // Else, find all possible split positions for split 1 and split 2.
+    let ones = 0, possStr1 = 0, possStr2 = 0, curr = 0, maxOnes = onesCount/3;
+    for (let idx = 0; idx < s.length; idx++) {
+        ones += s[idx] === '1' ? 1 : 0;
+        if (ones === maxOnes) possStr1++;
+        else if (ones === 2*maxOnes) possStr2++;
+    }
+    
+    return possStr1 * possStr2 % mod;
+};
+
+function countOnes(s: string): number {
+    let total = 0;
+    for (let idx = 0; idx < s.length; idx++) {
+        if (s[idx] === '1') total++;
+    }
+    return total;
+}
diff --git a/level_medium/LeetCode_351_Android_Unlock.ts b/level_medium/LeetCode_351_Android_Unlock.ts
@@ -0,0 +1,55 @@
+/**
+ * Leet Code 351
+ * 
+ * This is a backtracking problem, since all the possible permutations of elements needs to be figured out. However,
+ * each solution space is bound by few constraints which do not allow the solution to succeed. This is where we backtrack
+ * the solution space.
+ * 
+ * Time: O(n!) where n is at max 9, since all the possible permutations of that length is required.
+ * Space: O(n) since that is the max stack size.
+ * 
+ * @param m 
+ * @param n 
+ */
+function numberOfPatterns(m: number, n: number): number {
+    const result: {total: number} = {total: 0};
+    const used: boolean[] = Array(10).fill(false)
+    for (let stIdx = 1; stIdx <= 9; stIdx++) {
+        used[stIdx] = true
+        findNumberOfPatterns(m, n, stIdx, 1, used, result)
+        used[stIdx] = false
+    }
+    return result.total;
+};
+
+function findNumberOfPatterns(m: number, n: number, last: number, size: number, used: boolean[], result: {total: number}) {
+    
+    // If we have created a length in the target range, add to result.
+    if (size >= m && size <= n) result.total++
+    
+    // Terminating the branch if the total length exceeds.
+    if (size >= n) return
+    
+    for (let next = 1; next <= 9; next++) {
+        // if the next index is not used already and a valid move
+        if (!used[next] && isValid(last, next, used)) {
+            used[next] = true
+            findNumberOfPatterns(m, n, next, size + 1, used, result)
+            used[next] = false    
+        }
+    }
+}
+
+const JUMP_TABLE: number[][] = Array.from({length: 10}, () => Array(10))
+JUMP_TABLE[1][3] = JUMP_TABLE[3][1] = 2
+JUMP_TABLE[4][6] = JUMP_TABLE[6][4] = 5
+JUMP_TABLE[7][9] = JUMP_TABLE[9][7] = 8
+JUMP_TABLE[1][7] = JUMP_TABLE[7][1] = 4
+JUMP_TABLE[2][8] = JUMP_TABLE[8][2] = 5
+JUMP_TABLE[3][9] = JUMP_TABLE[9][3] = 6
+JUMP_TABLE[1][9] = JUMP_TABLE[9][1] = JUMP_TABLE[7][3] = JUMP_TABLE[3][7] = 5
+
+function isValid(last: number, next: number, used: boolean[]) {
+    const jump = JUMP_TABLE[next][last]
+    return jump === undefined || used[jump] === true
+}
diff --git a/level_medium/LeetCode_351_Android_Unlock_1.ts b/level_medium/LeetCode_351_Android_Unlock_1.ts
@@ -0,0 +1,62 @@
+/**
+ * Leet Code 351
+ * 
+ * This is a backtracking problem, since all the possible permutations of elements needs to be figured out. However,
+ * each solution space is bound by few constraints which do not allow the solution to succeed. This is where we backtrack
+ * the solution space.
+ * 
+ * Optimization over the existing backtracking solution is that we are not computing the result for each position. Rather,
+ * the solution is only calculated for few positions and multiplied for symmetry. 
+ * 
+ * Time: O(n!) where n is at max 9, since all the possible permutations of that length is required.
+ * Space: O(n) since that is the max stack size.
+ * 
+ * @param m 
+ * @param n 
+ */
+function numberOfPatterns(m: number, n: number): number {
+    let total = 0
+    const used: boolean[] = Array(10).fill(false)
+    total += 4 * findNumberOfPatterns(m, n, 1, 1, used)
+    total += 4 * findNumberOfPatterns(m, n, 2, 1, used)
+    total += findNumberOfPatterns(m, n, 5, 1, used)
+    return total;
+};
+
+function findNumberOfPatterns(m: number, n: number, last: number, size: number, used: boolean[]) {
+    
+    used[last] = true
+    let total = 0;
+    
+    // If we have created a length in the target range, add to result.
+    if (size >= m && size <= n) total++
+    
+    // Terminating the branch if the total length exceeds.
+    if (size >= n) return total
+    
+    for (let next = 1; next <= 9; next++) {
+        // if the next index is not used already and a valid move
+        if (!used[next] && isValid(last, next, used)) {
+            used[next] = true
+            total += findNumberOfPatterns(m, n, next, size + 1, used)
+            used[next] = false    
+        }
+    }
+    
+    used[last] = false
+    return total
+}
+
+const JUMP_TABLE: number[][] = Array.from({length: 10}, () => Array(10))
+JUMP_TABLE[1][3] = JUMP_TABLE[3][1] = 2
+JUMP_TABLE[4][6] = JUMP_TABLE[6][4] = 5
+JUMP_TABLE[7][9] = JUMP_TABLE[9][7] = 8
+JUMP_TABLE[1][7] = JUMP_TABLE[7][1] = 4
+JUMP_TABLE[2][8] = JUMP_TABLE[8][2] = 5
+JUMP_TABLE[3][9] = JUMP_TABLE[9][3] = 6
+JUMP_TABLE[1][9] = JUMP_TABLE[9][1] = JUMP_TABLE[7][3] = JUMP_TABLE[3][7] = 5
+
+function isValid(last: number, next: number, used: boolean[]) {
+    const jump = JUMP_TABLE[next][last]
+    return jump === undefined || used[jump] === true
+}
