Smallest non-zero substring which has any permutation divisible by 2^K
Given a binary string S of length N and an integer K, the task is to find the smallest non-zero sub-string of S that can be jumbled to produce a binary string divisible by 2K. If no such sub-string exists then print -1. Note that K is always greater than 0.
Examples:
Input: S = “100”, k = 1
Output: 2
Smallest substring that can be jumbled is “10”.
Thus, the answer is 2.
Input: S = “1111”, k = 2
Output: -1
Approach: Let’s look at the condition of the permutation of a string being divisible by 2K.
- The string must have at least K number of 0s.
- The string must have at least one 1.
This can be implemented using two-pointer technique. For every index i, try to find the smallest index j such that the substring S[i…j-1] satisfies the above two conditions.
Let’s say the left pointer is pointing at index i and the right pointer is pointing at j and ans stores the length of the smallest required substring.
If the condition is not satisfied then increment j, else increment i.
While iterating, find the minimum (j – i) satisfying the above two conditions and update the answer as ans = min(ans, j – i).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the length of the // smallest substring divisible by 2^k int findLength(string s, int k) { // To store the final answer int ans = INT_MAX; // Left pointer int l = 0; // Right pointer int r = 0; // Count of the number of zeros and // ones in the current substring int cnt_zero = 0, cnt_one = 0; // Loop for two pointers while (l < s.size() and r <= s.size()) { // Condition satisfied if (cnt_zero >= k and cnt_one >= 1) { // Updated the answer ans = min(ans, r - l); // Update the pointer and count l++; if (s[l - 1] == '0' ) cnt_zero--; else cnt_one--; } else { // Update the pointer and count if (r == s.size()) break ; if (s[r] == '0' ) cnt_zero++; else cnt_one++; r++; } } if (ans == INT_MAX) return -1; return ans; } // Driver code int main() { string s = "100" ; int k = 2; cout << findLength(s, k); return 0; } |
Java
// Java implementation of the approach class GFG { static final int INT_MAX = Integer.MAX_VALUE; // Function to return the length of the // smallest substring divisible by 2^k static int findLength(String s, int k) { // To store the final answer int ans = INT_MAX; // Left pointer int l = 0 ; // Right pointer int r = 0 ; // Count of the number of zeros and // ones in the current substring int cnt_zero = 0 , cnt_one = 0 ; // Loop for two pointers while (l < s.length() && r <= s.length()) { // Condition satisfied if (cnt_zero >= k && cnt_one >= 1 ) { // Updated the answer ans = Math.min(ans, r - l); // Update the pointer and count l++; if (s.charAt(l - 1 ) == '0' ) cnt_zero--; else cnt_one--; } else { // Update the pointer and count if (r == s.length()) break ; if (s.charAt(r) == '0' ) cnt_zero++; else cnt_one++; r++; } } if (ans == INT_MAX) return - 1 ; return ans; } // Driver code public static void main (String[] args) { String s = "100" ; int k = 2 ; System.out.println(findLength(s, k)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the length of the # smallest subdivisible by 2^k def findLength(s, k): # To store the final answer ans = 10 * * 9 # Left pointer l = 0 # Right pointer r = 0 # Count of the number of zeros and # ones in the current substring cnt_zero = 0 cnt_one = 0 # Loop for two pointers while (l < len (s) and r < = len (s)): # Condition satisfied if (cnt_zero > = k and cnt_one > = 1 ): # Updated the answer ans = min (ans, r - l) # Update the pointer and count l + = 1 if (s[l - 1 ] = = '0' ): cnt_zero - = 1 else : cnt_one - = 1 else : # Update the pointer and count if (r = = len (s)): break if (s[r] = = '0' ): cnt_zero + = 1 else : cnt_one + = 1 r + = 1 if (ans = = 10 * * 9 ): return - 1 return ans # Driver code s = "100" k = 2 print (findLength(s, k)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { static int INT_MAX = int .MaxValue; // Function to return the length of the // smallest substring divisible by 2^k static int findLength( string s, int k) { // To store the final answer int ans = INT_MAX; // Left pointer int l = 0; // Right pointer int r = 0; // Count of the number of zeros and // ones in the current substring int cnt_zero = 0, cnt_one = 0; // Loop for two pointers while (l < s.Length && r <= s.Length) { // Condition satisfied if (cnt_zero >= k && cnt_one >= 1) { // Updated the answer ans = Math.Min(ans, r - l); // Update the pointer and count l++; if (s[l - 1] == '0' ) cnt_zero--; else cnt_one--; } else { // Update the pointer and count if (r == s.Length) break ; if (s[r] == '0' ) cnt_zero++; else cnt_one++; r++; } } if (ans == INT_MAX) return -1; return ans; } // Driver code public static void Main () { string s = "100" ; int k = 2; Console.WriteLine(findLength(s, k)); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach // Function to return the length of the // smallest substring divisible by 2^k function findLength(s, k) { // To store the final answer var ans = 1000000000; // Left pointer var l = 0; // Right pointer var r = 0; // Count of the number of zeros and // ones in the current substring var cnt_zero = 0, cnt_one = 0; // Loop for two pointers while (l < s.length && r <= s.length) { // Condition satisfied if (cnt_zero >= k && cnt_one >= 1) { // Updated the answer ans = Math.min(ans, r - l); // Update the pointer and count l++; if (s[l - 1] == '0' ) cnt_zero--; else cnt_one--; } else { // Update the pointer and count if (r == s.length) break ; if (s[r] == '0' ) cnt_zero++; else cnt_one++; r++; } } if (ans == 1000000000) return -1; return ans; } // Driver code var s = "100" ; var k = 2; document.write( findLength(s, k)); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)