Given a binary string S of size N and three positive integers L, R, and K, the task is to find the minimum number of swaps required to such that the substring {S[L], .. S[R]} consists of exactly K 1s. If it is not possible to do so, then print “-1”.
Examples:
Input: S = “110011111000101”, L = 5, R = 8, K = 2
Output: 2
Explanation:
Initially, the substring {S[5], .. S[8]} = “1111” consists of 4 1s.
Swap (S[5], S[3]) and (S[6], S[4]).
Modified string S = “111100111000101” and {S[5], .. S[8]} = “0011”.
Therefore, 2 swaps are required.Input: S = “01010101010101”, L = 3, R = 7, K = 8
Output: -1
Approach: The idea is to count the number of 1s and 0s present in the substring and outside the substring, {S[L], …, S[R]}. Then, check if enough 1s or 0s are present outside that range which can be swapped such that the substring contains exactly K 1s.
Follow the steps below to solve the problem:
- Store the frequency of 1s and 0s in the string S in cntOnes and cntZeros respectively.
- Also, store the frequency of 1s and 0s in the substring S[L, R] in ones and zeros respectively.
- Find the frequency of 1s and 0s outside the substring S[L, R] using the formula: (rem_ones = cntOnes – ones) and rem_zero = (cntZeros – zeros).
- If k ? ones, then do the following:
- Initialize rem = (K – ones), which denotes the number of 1s required to make the sum equal to K.
- If zeros ? rem and rem_ones ? rem, print the value of rem as the result.
- Otherwise, if K < ones, then do the following:
- Initialize rem = (ones – K), which denotes the number of 0s required to make the sum equal to K.
- If ones ? rem and rem_zeros ? rem, print the value of rem as the result.
- In all other cases, print -1.
Below is the implementation of the above approach:
C++
// CPP program for the above approach#include<bits/stdc++.h>using namespace std; // Function to find the minimum number // of swaps required such that the // substring {s[l], .., s[r]} consists // of exactly k 1s int minimumSwaps(string s, int l, int r, int k) { // Store the size of the string int n = s.length(); // Store the total number of 1s // and 0s in the entire string int tot_ones = 0, tot_zeros = 0; // Traverse the string S to find // the frequency of 1 and 0 for (int i = 0; i < s.length(); i++) { if (s[i] == '1') tot_ones++; else tot_zeros++; } // Store the number of 1s and // 0s in the substring s[l, r] int ones = 0, zeros = 0, sum = 0; // Traverse the substring S[l, r] // to find the frequency of 1s // and 0s in it for (int i = l - 1; i < r; i++) { if (s[i] == '1') { ones++; sum++; } else zeros++; } // Store the count of 1s and // 0s outside substring s[l, r] int rem_ones = tot_ones - ones; int rem_zeros = tot_zeros - zeros; // Check if the sum of the // substring is at most K if (k >= sum) { // Store number of 1s required int rem = k - sum; // Check if there are enough 1s // remaining to be swapped if (zeros >= rem && rem_ones >= rem) return rem; } // If the count of 1s in the substring exceeds k else if (k < sum) { // Store the number of 0s required int rem = sum - k; // Check if there are enough 0s // remaining to be swapped if (ones >= rem && rem_zeros >= rem) return rem; } // In all other cases, print -1 return -1; } // Driver Code int main() { string S = "110011111000101"; int L = 5, R = 8, K = 2; cout<<minimumSwaps(S, L, R, K); }// This code is contributed bgangwar59. |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find the minimum number // of swaps required such that the // substring {s[l], .., s[r]} consists // of exactly k 1s static int minimumSwaps( String s, int l, int r, int k) { // Store the size of the string int n = s.length(); // Store the total number of 1s // and 0s in the entire string int tot_ones = 0, tot_zeros = 0; // Traverse the string S to find // the frequency of 1 and 0 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1') tot_ones++; else tot_zeros++; } // Store the number of 1s and // 0s in the substring s[l, r] int ones = 0, zeros = 0, sum = 0; // Traverse the substring S[l, r] // to find the frequency of 1s // and 0s in it for (int i = l - 1; i < r; i++) { if (s.charAt(i) == '1') { ones++; sum++; } else zeros++; } // Store the count of 1s and // 0s outside substring s[l, r] int rem_ones = tot_ones - ones; int rem_zeros = tot_zeros - zeros; // Check if the sum of the // substring is at most K if (k >= sum) { // Store number of 1s required int rem = k - sum; // Check if there are enough 1s // remaining to be swapped if (zeros >= rem && rem_ones >= rem) return rem; } // If the count of 1s in the substring exceeds k else if (k < sum) { // Store the number of 0s required int rem = sum - k; // Check if there are enough 0s // remaining to be swapped if (ones >= rem && rem_zeros >= rem) return rem; } // In all other cases, print -1 return -1; } // Driver Code public static void main(String[] args) { String S = "110011111000101"; int L = 5, R = 8, K = 2; System.out.println( minimumSwaps(S, L, R, K)); }} |
Python3
# Python3 program for the above approach# Function to find the minimum number# of swaps required such that the# substring {s[l], .., s[r]} consists# of exactly k 1sdef minimumSwaps(s, l, r, k) : # Store the size of the string n = len(s) # Store the total number of 1s # and 0s in the entire string tot_ones, tot_zeros = 0, 0 # Traverse the string S to find # the frequency of 1 and 0 for i in range(0, len(s)) : if (s[i] == '1') : tot_ones += 1 else : tot_zeros += 1 # Store the number of 1s and # 0s in the substring s[l, r] ones, zeros, Sum = 0, 0, 0 # Traverse the substring S[l, r] # to find the frequency of 1s # and 0s in it for i in range(l - 1, r) : if (s[i] == '1') : ones += 1 Sum += 1 else : zeros += 1 # Store the count of 1s and # 0s outside substring s[l, r] rem_ones = tot_ones - ones rem_zeros = tot_zeros - zeros # Check if the sum of the # substring is at most K if (k >= Sum) : # Store number of 1s required rem = k - Sum # Check if there are enough 1s # remaining to be swapped if (zeros >= rem and rem_ones >= rem) : return rem # If the count of 1s in the substring exceeds k elif (k < Sum) : # Store the number of 0s required rem = Sum - k # Check if there are enough 0s # remaining to be swapped if (ones >= rem and rem_zeros >= rem) : return rem # In all other cases, print -1 return -1S = "110011111000101"L, R, K = 5, 8, 2print(minimumSwaps(S, L, R, K))# This code is contributed by divyeshrabadiya07. |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to find the minimum number // of swaps required such that the // substring {s[l], .., s[r]} consists // of exactly k 1s static int minimumSwaps(string s, int l, int r, int k) { // Store the size of the string int n = s.Length; // Store the total number of 1s // and 0s in the entire string int tot_ones = 0, tot_zeros = 0; // Traverse the string S to find // the frequency of 1 and 0 for (int i = 0; i < s.Length; i++) { if (s[i] == '1') tot_ones++; else tot_zeros++; } // Store the number of 1s and // 0s in the substring s[l, r] int ones = 0, zeros = 0, sum = 0; // Traverse the substring S[l, r] // to find the frequency of 1s // and 0s in it for (int i = l - 1; i < r; i++) { if (s[i] == '1') { ones++; sum++; } else zeros++; } // Store the count of 1s and // 0s outside substring s[l, r] int rem_ones = tot_ones - ones; int rem_zeros = tot_zeros - zeros; // Check if the sum of the // substring is at most K if (k >= sum) { // Store number of 1s required int rem = k - sum; // Check if there are enough 1s // remaining to be swapped if (zeros >= rem && rem_ones >= rem) return rem; } // If the count of 1s in the substring exceeds k else if (k < sum) { // Store the number of 0s required int rem = sum - k; // Check if there are enough 0s // remaining to be swapped if (ones >= rem && rem_zeros >= rem) return rem; } // In all other cases, print -1 return -1; } // Driver Code public static void Main(String[] args) { string S = "110011111000101"; int L = 5, R = 8, K = 2; Console.Write(minimumSwaps(S, L, R, K)); }}// This code is contributed by splevel62. |
Javascript
<script>// javascript program for the above approach// Function to find the minimum number// of swaps required such that the// substring {s[l], .., s[r]} consists// of exactly k 1sfunction minimumSwaps(s , l , r , k){ // Store the size of the string var n = s.length; // Store the total number of 1s // and 0s in the entire string var tot_ones = 0, tot_zeros = 0; // Traverse the string S to find // the frequency of 1 and 0 for (i = 0; i < s.length; i++) { if (s.charAt(i) == '1') tot_ones++; else tot_zeros++; } // Store the number of 1s and // 0s in the substring s[l, r] var ones = 0, zeros = 0, sum = 0; // Traverse the substring S[l, r] // to find the frequency of 1s // and 0s in it for (var i = l - 1; i < r; i++) { if (s.charAt(i) == '1') { ones++; sum++; } else zeros++; } // Store the count of 1s and // 0s outside substring s[l, r] var rem_ones = tot_ones - ones; var rem_zeros = tot_zeros - zeros; // Check if the sum of the // substring is at most K if (k >= sum) { // Store number of 1s required var rem = k - sum; // Check if there are enough 1s // remaining to be swapped if (zeros >= rem && rem_ones >= rem) return rem; } // If the count of 1s in the substring exceeds k else if (k < sum) { // Store the number of 0s required var rem = sum - k; // Check if there are enough 0s // remaining to be swapped if (ones >= rem && rem_zeros >= rem) return rem; } // In all other cases, print -1 return -1;}// Driver Codevar S = "110011111000101";var L = 5, R = 8, K = 2;document.write( minimumSwaps(S, L, R, K));// This code is contributed by 29AjayKumar </script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
