# Minimum replacements in a string to make adjacent characters unequal

Given a lowercase character string **str** of size **N**. In one operation any character can be changed into some other character. The task is to find the minimum number of operations such that no two adjacent characters are equal.**Examples:**

Input:Str = “caaab”Output:1Explanation:

Change the secondato any other character, let’s change it tob. So the string becomes “cabab”. and no two adjacent characters are equal. So minimum number of operations is 1.Input:Str = “xxxxxxx”Output:3Explanation:

Replace ‘x’ at index 1, 3 and 5 to ‘a’, ‘b’, and ‘c’ respectively.Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Approach: ** The idea is similar to implement sliding window technique. In this, we need to find the non-overlapping substrings that have all the characters the same. Then the minimum operations will be the sum of the floor of half the length of each substring.

- There is no need to change a character directly. Instead, consider all substring started from any index having only one character.
- Now consider any substring of length
**l**such that all the characters of that substring are equal then change**floor ( l / 2)**characters of this substring to some other character. - So just iterate over all the characters of the string from any character
**ch**find out the maximal length of the substring such that all the characters in that substring are equal to the character**ch**. **Find the length l of this substring and add floor ( l / 2) to the ans**.- After that start from the character just next to the end of the above substring.

## C++14

`// C++ program to find minimum` `// replacements in a string to` `// make adjacent characters unequal` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function which counts the minimum` `// number of required operations` `void` `count_minimum(string s)` `{` ` ` `// n stores the length of the string s` ` ` `int` `n = s.length();` ` ` `// ans will store the required ans` ` ` `int` `ans = 0;` ` ` `// i is the current index in the string` ` ` `int` `i = 0;` ` ` `while` `(i < n) {` ` ` `int` `j = i;` ` ` `// Move j until characters s[i] & s[j]` ` ` `// are equal or the end of the` ` ` `// string is reached` ` ` `while` `(s[j] == s[i] && j < n) {` ` ` `j++;` ` ` `}` ` ` `// diff stores the length of the` ` ` `// substring such that all the` ` ` `// characters are equal in it` ` ` `int` `diff = j - i;` ` ` `// We need atleast diff/2 operations` ` ` `// for this substring` ` ` `ans += diff / 2;` ` ` `i = j;` ` ` `}` ` ` `cout << ans << endl;` `}` `// Driver code` `int` `main()` `{` ` ` `string str = ` `"caaab"` `;` ` ` `count_minimum(str);` ` ` `return` `0;` `}` |

## Java

`// Java program to find minimum` `// replacements in a string to` `// make adjacent characters unequal` `import` `java.util.*;` `class` `GFG{` `// Function which counts the minimum` `// number of required operations` `static` `void` `count_minimum(String s)` `{` ` ` ` ` `// n stores the length of the string s` ` ` `int` `n = s.length();` ` ` `// ans will store the required ans` ` ` `int` `ans = ` `0` `;` ` ` `// i is the current index in the string` ` ` `int` `i = ` `0` `;` ` ` `while` `(i < n)` ` ` `{` ` ` `int` `j = i;` ` ` `// Move j until characters s[i] & s[j]` ` ` `// are equal or the end of the` ` ` `// string is reached` ` ` `while` `(j < n && s.charAt(j) ==` ` ` `s.charAt(i))` ` ` `{` ` ` `j++;` ` ` `}` ` ` `// diff stores the length of the` ` ` `// substring such that all the` ` ` `// characters are equal in it` ` ` `int` `diff = j - i;` ` ` `// We need atleast diff/2 operations` ` ` `// for this substring` ` ` `ans += diff / ` `2` `;` ` ` `i = j;` ` ` `}` ` ` `System.out.println(ans);` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `String str = ` `"caaab"` `;` ` ` `count_minimum(str);` `}` `}` `// This code is contributed by offbeat` |

## Python3

`# Python3 program to find minimum` `# replacements in a string to` `# make adjacent characters unequal` `# Function which counts the minimum` `# number of required operations` `def` `count_minimum(s):` ` ` ` ` `# n stores the length of the string s` ` ` `n ` `=` `len` `(s)` ` ` `# ans will store the required ans` ` ` `ans ` `=` `0` ` ` ` ` `# i is the current index in the string` ` ` `i ` `=` `0` ` ` ` ` `while` `i < n:` ` ` `j ` `=` `i` ` ` ` ` `# Move j until characters s[i] & s[j]` ` ` `# are equal or the end of the` ` ` `# string is reached` ` ` `while` `j < n ` `and` `(s[j] ` `=` `=` `s[i]):` ` ` `j ` `+` `=` `1` ` ` ` ` `# diff stores the length of the` ` ` `# substring such that all the` ` ` `# characters are equal in it` ` ` `diff ` `=` `j ` `-` `i` ` ` ` ` `# We need atleast diff/2 operations` ` ` `# for this substring` ` ` `ans ` `+` `=` `diff ` `/` `/` `2` ` ` `i ` `=` `j` ` ` ` ` `print` `(ans)` ` ` `# Driver code` `if` `__name__` `=` `=` `"__main__"` `:` ` ` ` ` `str` `=` `"caaab"` ` ` `count_minimum(` `str` `)` ` ` `# This code is contributed by rutvik_56` |

## C#

`// C# program to find minimum` `// replacements in a string to` `// make adjacent characters unequal` `using` `System;` `class` `GFG{` ` ` `// Function which counts the minimum` `// number of required operations` `static` `void` `count_minimum(` `string` `s)` `{` ` ` ` ` `// n stores the length of the string s` ` ` `int` `n = s.Length;` ` ` `// ans will store the required ans` ` ` `int` `ans = 0;` ` ` `// i is the current index in the string` ` ` `int` `i = 0;` ` ` `while` `(i < n)` ` ` `{` ` ` `int` `j = i;` ` ` `// Move j until characters s[i] & s[j]` ` ` `// are equal or the end of the` ` ` `// string is reached` ` ` `while` `(j < n && s[j] == s[i])` ` ` `{` ` ` `j++;` ` ` `}` ` ` `// diff stores the length of the` ` ` `// substring such that all the` ` ` `// characters are equal in it` ` ` `int` `diff = j - i;` ` ` `// We need atleast diff/2 operations` ` ` `// for this substring` ` ` `ans += diff / 2;` ` ` `i = j;` ` ` `}` ` ` `Console.WriteLine(ans);` `}` `// Driver code` `static` `void` `Main()` `{` ` ` `string` `str = ` `"caaab"` `;` ` ` ` ` `count_minimum(str);` `}` `}` `// This code is contributed by divyeshrabadiya07` |

## Javascript

`<script>` ` ` `// JavaScript program to find minimum` ` ` `// replacements in a string to` ` ` `// make adjacent characters unequal` ` ` `// Function which counts the minimum` ` ` `// number of required operations` ` ` `function` `count_minimum(s) {` ` ` `// n stores the length of the string s` ` ` `var` `n = s.length;` ` ` `// ans will store the required ans` ` ` `var` `ans = 0;` ` ` `// i is the current index in the string` ` ` `var` `i = 0;` ` ` `while` `(i < n) {` ` ` `var` `j = i;` ` ` `// Move j until characters s[i] & s[j]` ` ` `// are equal or the end of the` ` ` `// string is reached` ` ` `while` `(s[j] === s[i] && j < n) {` ` ` `j++;` ` ` `}` ` ` `// diff stores the length of the` ` ` `// substring such that all the` ` ` `// characters are equal in it` ` ` `var` `diff = j - i;` ` ` `// We need atleast diff/2 operations` ` ` `// for this substring` ` ` `ans += parseInt(diff / 2);` ` ` `i = j;` ` ` `}` ` ` `document.write(ans + ` `"<br>"` `);` ` ` `}` ` ` `// Driver code` ` ` `var` `str = ` `"caaab"` `;` ` ` `count_minimum(str);` ` ` `</script>` |

**Output**

1

**Time Complexity:** O (N)

**Auxiliary Space: **O (1)