Given a string S, change the smallest number of letters in S such that all adjacent characters are different. Print the resultant string.
Examples :
Input : S = "aab" Output: acb Explanation : Loop will start for i-th character, which is second ‘a’. It’s cannot be ‘b’ since it matches with third char. So output should be ‘acb’. Input : S = "neveropen" Output: geaksforgeaks Explanation : Resultant string, after making minimal changes. S = "geaksforgeaks". We made two changes, which is the optimal solution here.
We can solve this problem using greedy approach. Let us consider a segment of length k of consecutive identical characters. We have to make at least [K/2] changes in the segment, to make that there are no identical characters in a row. We can also change the second, fourth etc.. characters of the string that is it should not be equal to the letter on the left side and the letter to the right side.
Traverse the string from starting index (i = 1) and if any two adjacent letters( i & i-1) are equal then initialize (i)th character with ‘a’ and start another loop to make (i)th character different from the left and right letters.
Below is the implementation of above approach :
C++
// C++ program to print a string with no adjacent// duplicates by doing minimum changes to original// string#include <bits/stdc++.h>using namespace std;// Function to print simple stringstring noAdjacentDup(string s){ int n = s.length(); for (int i = 1; i < n; i++) { // If any two adjacent characters are equal if (s[i] == s[i - 1]) { s[i] = 'a'; // Initialize it to 'a' // Traverse the loop until it is different // from the left and right letter. while (s[i] == s[i - 1] || (i + 1 < n && s[i] == s[i + 1])) s[i]++; i++; } } return s;}// Driver Functionint main(){ string s = "neveropen"; cout << noAdjacentDup(s); return 0;} |
Java
// Java program to print a string with// no adjacent duplicates by doing // minimum changes to original stringimport java.util.*;import java.lang.*;public class GfG{ // Function to print simple string public static String noAdjacentDup(String s1) { int n = s1.length(); char[] s = s1.toCharArray(); for (int i = 1; i < n; i++) { // If any two adjacent // characters are equal if (s[i] == s[i - 1]) { // Initialize it to 'a' s[i] = 'a'; // Traverse the loop until it // is different from the left // and right letter. while (s[i] == s[i - 1] || (i + 1 < n && s[i] == s[i + 1])) s[i]++; i++; } } return (new String(s)); } // Driver function public static void main(String argc[]){ String s = "neveropen"; System.out.println(noAdjacentDup(s)); } }/* This code is contributed by Sagar Shukla */ |
Python3
# Python program to print a string with# no adjacent duplicates by doing minimum # changes to original string# Function to print simple stringdef noAdjacentDup(s): n = len(s) for i in range(1, n): # If any two adjacent characters are equal if (s[i] == s[i - 1]): s[i] = "a" # Initialize it to 'a' # Traverse the loop until it is different # from the left and right letter. while (s[i] == s[i - 1] or (i + 1 < n and s[i] == s[i + 1])): s[i] += 1 i += 1 return s# Driver Functions = list("neveropen")print("".join(noAdjacentDup(s)))# This code is contributed by Anant Agarwal. |
C#
// C# program to print a string with// no adjacent duplicates by doing // minimum changes to original stringusing System;class GfG{ // Function to print simple string public static String noAdjacentDup(String s1) { int n = s1.Length; char[] s = s1.ToCharArray(); for (int i = 1; i < n; i++) { // If any two adjacent // characters are equal if (s[i] == s[i - 1]) { // Initialize it to 'a' s[i] = 'a'; // Traverse the loop until it // is different from the left // and right letter. while (s[i] == s[i - 1] || (i + 1 < n && s[i] == s[i + 1])) s[i]++; i++; } } return (new String(s)); } // Driver function public static void Main(String[] argc) { String s = "neveropen"; // Function calling Console.Write(noAdjacentDup(s)); }}/* This code is contributed by parashar */ |
PHP
<?php// PHP program to print a // string with no adjacent// duplicates by doing minimum // changes to original string// Function to print// simple stringfunction noAdjacentDup($s){ $n = strlen($s); for ($i = 1; $i < $n; $i++) { // If any two adjacent // characters are equal if ($s[$i] == $s[$i - 1]) { // Initialize it to 'a' $s[$i] = 'a'; // Traverse the loop // until it is different // from the left and // right letter. while ($s[$i] == $s[$i - 1] || ($i + 1 < $n && $s[$i] == $s[$i + 1])) $s[$i]++; $i++; } } return $s;}// Driver Code$s = "neveropen";echo (noAdjacentDup($s));// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// Javascript program to print a string with// no adjacent duplicates by doing // minimum changes to original string // Function to print simple string function noAdjacentDup(s1) { let n = s1.length; let s = s1.split(''); for (let i = 1; i < n; i++) { // If any two adjacent // characters are equal if (s[i] == s[i - 1]) { // Initialize it to 'a' s[i] = 'a'; // Traverse the loop until it // is different from the left // and right letter. while (s[i] == s[i - 1] || (i + 1 < n && s[i] == s[i + 1])) s[i]++; i++; } } return (s); }// driver code let s = "neveropen"; document.write(noAdjacentDup(s));</script> |
Output
geaksforgeaks
Time Complexity: O(N2)
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!
