1

Minimum number of swaps required such that a given substring consists of exactly...

 11 months ago
source link: https://www.geeksforgeeks.org/minimum-number-of-swaps-required-such-that-a-given-substring-consists-of-exactly-k-1s/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Minimum number of swaps required such that a given substring consists of exactly K 1s

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:

  • Python3
  • Javascript
// 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.
Output: 
2

Time Complexity: O(N)
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK