JavaScript Program for Min flips of continuous characters to make all characters same in a String
In this article, we will learn about Min flips of continuous characters to make all characters the same in a string using JavaScript. Min flips of continuous characters in a string refer to the minimum number of changes required to turn a sequence of adjacent characters into a uniform sequence, ensuring all characters are the same. Given a string consisting only of 1’s and 0’s. In one flip we can change any continuous sequence of this string.
Example:
Input : 00011110001110
Output : 2
We need to convert 1's sequence
so string consist of all 0's.
Input : 010101100011
Output : 4
Table of Content
- Using regular expression
- Using for…in loop
We will explore all the above methods along with their basic implementation with the help of examples.
Using regular expression
In this approach, regular expression pattern (/([01])\1*/g) is used to find continuous sequences of the same characters (0s and 1s) in the input String. These matches are then counted to determine the minimum flips needed to make all characters the same.
Syntax
const regex = /([01])\1*/g;
Example: In this example, we use a regular expression to group consecutive ‘0’ or ‘1’ characters. It counts flips by subtracting one from each group’s length and totals them. Result: 4 flips.
const inputStr = "010101100011";
const regex = /([01])\1*/g;
const result = inputStr.match(regex) || [];
let flips = 0;
for (const match of result) {
flips += match.length - 1;
}
console.log("Minimum flips needed :", flips);
Output
Minimum flips needed : 4
Using for…in loop
In this approach, we use for in loop in which we count minimum flips by iterating through inputStr. It compares each character with the next, incrementing flips when they differ, and finding the minimum flips required.
Syntax
for (let i in obj1) {
console.log(i);
};
Example: In this example, we are using for…in loop to count flips needed to alternate ‘0’ and ‘1’ in “010101100011.” If a digit differs from the expected, a flip is counted.
let inputStr = "010101100011";
let result = 0;
for (let i in inputStr) {
if (i % 2 === 0 &&
inputStr[i] !== '0') {
result++;
} else if (i % 2 === 1 &&
inputStr[i] !== '1') {
result++;
}
}
console.log("Minimum flips needed:", result);
Output
Minimum flips needed: 4
Using Two Pointers
Using two pointers, the approach iterates through the string, moving one pointer until it reaches a different character. Then it calculates flips needed for each group of consecutive characters, minimizing the total flips required.
Example: In this example the function calculates the minimum flips needed to make all consecutive characters in a string the same.
function minFlipsToMakeAllSame(str) {
let flips = 0;
for (let i = 0, j = 0; i < str.length; i = j) {
while (j < str.length && str[j] === str[i]) {
j++;
}
flips++;
}
return Math.min(flips, str.length - flips);
}
console.log(minFlipsToMakeAllSame("00110011")); // 4
Output
4