Given a binary string s and an array ct[] of even size. The task is to minimize the cost of operations to:
- Convert string s to a string of either type XYXYXYXYXY… or XXYYXXYYXXYY…
- In one operation it is allowed to flip ith character with cost ct[i].
Examples
Input: s = “1011” ct = {1, 2, 1, 3}
Output: 1
Explanation: Follow operations are performed to convert s to given format:
Flip the 0th bit from 1 to 0, the updated s = “0011” which is in the form XXYY.
Hence, 1 is the answer which is minimum possible.Input: “1010”
Output: 0
Explanation: The string is already in a given format.
Approach: This problem is observation-based. Follow the steps below to solve the given problem.
- There are only four types of binary strings, according to the problem.
- 010101010101…….
- 101010101010…….
- 001100110011……..
- 110011001100……..
- We have to check for these four different strings only.
- Pass the string along with cost and the first four expected characters.
- If the expected characters do not match with the string’s actual characters then add the cost corresponding to the ith value.
- Repeat the procedure for all four expected sequences and choose the minimum cost out of it.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;int solve_util(string s, int c[], char x, char y, char z, char w){ int ans = 0; for (int i = 0; i < s.length(); i += 4) { if (s[i] != x) ans += c[i]; if (i + 1 < s.length() && s[i + 1] != y) ans += c[i + 1]; if (i + 2 < s.length() && s[i + 2] != z) ans += c[i + 2]; if (i + 3 < s.length() && s[i + 3] != w) ans += c[i + 3]; } return ans;}int solve_util2(string s, int c[], char x, char y){ int ans = 0; if (s[0] != x) ans += c[0]; if (s[1] != y) ans += c[1]; return ans;}// Function to convert given// string to required formint minOperations(int N, string S, int C[]){ // code here if (S.length() == 2) { int x = solve_util2( S, C, '0', '1'); int y = solve_util2( S, C, '1', '0'); int z = solve_util2( S, C, '1', '1'); int w = solve_util2( S, C, '0', '0'); return min({ x, y, z, w }); } int x = solve_util( S, C, '0', '1', '0', '1'); int y = solve_util( S, C, '1', '0', '1', '0'); int z = solve_util( S, C, '1', '1', '0', '0'); int w = solve_util( S, C, '0', '0', '1', '1'); return min({ x, y, z, w });}// Driver Codeint main(){ int N = 4; string s = "1011"; int ct[] = { 1, 2, 1, 3 }; cout << minOperations(N, s, ct) << "\n"; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { static int solve_util(char s[], int c[], char x, char y, char z, char w) { int ans = 0; for (int i = 0; i < s.length; i += 4) { if (s[i] != x) ans += c[i]; if (i + 1 < s.length && s[i + 1] != y) ans += c[i + 1]; if (i + 2 < s.length && s[i + 2] != z) ans += c[i + 2]; if (i + 3 < s.length && s[i + 3] != w) ans += c[i + 3]; } return ans; } static int solve_util2(char s[], int c[], char x, char y) { int ans = 0; if (s[0] != x) ans += c[0]; if (s[1] != y) ans += c[1]; return ans; } // Function to convert given // string to required form static int minOperations(int N, char S[], int C[]) { // code here if (S.length == 2) { int x = solve_util2( S, C, '0', '1'); int y = solve_util2( S, C, '1', '0'); int z = solve_util2( S, C, '1', '1'); int w = solve_util2( S, C, '0', '0'); return Math.min(x, Math.min( y, Math.min(z, w ))); } int x = solve_util( S, C, '0', '1', '0', '1'); int y = solve_util( S, C, '1', '0', '1', '0'); int z = solve_util( S, C, '1', '1', '0', '0'); int w = solve_util( S, C, '0', '0', '1', '1'); return Math.min(x, Math.min( y, Math.min(z, w ))); } // Driver Code public static void main (String[] args) { int N = 4; char s[] = {'1', '0', '1', '1'}; int ct[] = { 1, 2, 1, 3 }; System.out.print(minOperations(N, s, ct)); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python program for above approachdef solve_util(s, c, x, y, z, w): ans = 0 for i in range(0, len(s), 4): if (s[i] != x): ans += c[i] if (i + 1 < len(s) and s[i + 1] != y): ans += c[i + 1] if (i + 2 < len(s) and s[i + 2] != z): ans += c[i + 2] if (i + 3 < len(s) and s[i + 3] != w): ans += c[i + 3] return ansdef solve_util2(s, c, x, y): ans = 0 if (s[0] != x): ans += c[0] if (s[1] != y): ans += c[1] return ans# Function to convert given# string to required formdef minOperations(N, S, C): # code here if (len(S) == 2): x = solve_util2(S, C, '0', '1') y = solve_util2(S, C, '1', '0') z = solve_util2(S, C, '1', '1') w = solve_util2(S, C, '0', '0') print(f"{x},{y},{z},{w}") return min([x, y, z, w]) x = solve_util(S, C, '0', '1', '0', '1') y = solve_util(S, C, '1', '0', '1', '0') z = solve_util(S, C, '1', '1', '0', '0') w = solve_util(S, C, '0', '0', '1', '1') return min([x, y, z, w])# Driver CodeN = 4s = "1011"ct = [1, 2, 1, 3]print(minOperations(N, s, ct))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ static int solve_util(char []s, int []c, char x, char y, char z, char w) { int ans = 0; for (int i = 0; i < s.Length; i += 4) { if (s[i] != x) ans += c[i]; if (i + 1 < s.Length && s[i + 1] != y) ans += c[i + 1]; if (i + 2 < s.Length && s[i + 2] != z) ans += c[i + 2]; if (i + 3 < s.Length && s[i + 3] != w) ans += c[i + 3]; } return ans; } static int solve_util2(char []s, int []c, char x, char y) { int ans = 0; if (s[0] != x) ans += c[0]; if (s[1] != y) ans += c[1]; return ans; } // Function to convert given // string to required form static int minOperations(int N, char []S, int []C) { // code here if (S.Length == 2) { int x = solve_util2( S, C, '0', '1'); int y = solve_util2( S, C, '1', '0'); int z = solve_util2( S, C, '1', '1'); int w = solve_util2( S, C, '0', '0'); return Math.Min(x, Math.Min( y, Math.Min(z, w ))); } else { int x = solve_util( S, C, '0', '1', '0', '1'); int y = solve_util( S, C, '1', '0', '1', '0'); int z = solve_util( S, C, '1', '1', '0', '0'); int w = solve_util( S, C, '0', '0', '1', '1'); return Math.Min(x, Math.Min( y, Math.Min(z, w ))); } } // Driver Code public static void Main () { int N = 4; char []s = {'1', '0', '1', '1'}; int []ct = { 1, 2, 1, 3 }; Console.Write(minOperations(N, s, ct)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach const solve_util = (s, c, x, y, z, w) => { let ans = 0; for (let i = 0; i < s.length; i += 4) { if (s[i] != x) ans += c[i]; if (i + 1 < s.length && s[i + 1] != y) ans += c[i + 1]; if (i + 2 < s.length && s[i + 2] != z) ans += c[i + 2]; if (i + 3 < s.length && s[i + 3] != w) ans += c[i + 3]; } return ans; } const solve_util2 = (s, c, x, y) => { let ans = 0; if (s[0] != x) ans += c[0]; if (s[1] != y) ans += c[1]; return ans; } // Function to convert given // string to required form const minOperations = (N, S, C) => { // code here if (S.length == 2) { let x = solve_util2(S, C, '0', '1'); let y = solve_util2(S, C, '1', '0'); let z = solve_util2(S, C, '1', '1'); let w = solve_util2(S, C, '0', '0'); document.write(`${x},${y},${z},${w}`); return Math.min(...[x, y, z, w]); } let x = solve_util(S, C, '0', '1', '0', '1'); let y = solve_util(S, C, '1', '0', '1', '0'); let z = solve_util(S, C, '1', '1', '0', '0'); let w = solve_util(S, C, '0', '0', '1', '1'); return Math.min(...[x, y, z, w]); } // Driver Code let N = 4; let s = "1011"; let ct = [1, 2, 1, 3]; document.write(minOperations(N, s, ct)); // This code is contributed by rakeshsahni</script> |
Output
1
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!
Share your thoughts in the comments
