Print a closest string that does not contain adjacent duplicates
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 = “w3wiki”
Output: geaksforgeaks
Explanation: Resultant string, after making minimal changes. S = “geaksforgeaks”. We made two changes, which is the optimal solution here.
Print a closest string that does not contain adjacent duplicates using Greedy Algorithm:
This problem can be solved 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.
Step-by-step approach:
- Iterates through the string from the second character (i = 1) to the end (i < n).
- For each character, it checks if the current character (s[i]) is the same as the previous character (s[i – 1]).
- If the characters are the same, the current character (s[i]) is set to ‘a’ (the first character in the ASCII sequence).
- Then, a nested loop is used to increment the current character (s[i]) until it is different from both the previous (s[i – 1]) and the next (s[i + 1]) characters, if the next character exists.
- The outer loop index i is incremented by 1 to skip the modified character.
- Finally, the modified string is returned.
Below is the implementation of above approach:
// 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 string
string 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 Function
int main()
{
string s = "w3wiki";
cout << noAdjacentDup(s);
return 0;
}
// Java program to print a string with
// no adjacent duplicates by doing
// minimum changes to original string
import 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 = "w3wiki";
System.out.println(noAdjacentDup(s));
}
}
/* This code is contributed by Sagar Shukla */
# Python program to print a string with
# no adjacent duplicates by doing minimum
# changes to original string
# Function to print simple string
def 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 Function
s = list("w3wiki")
print("".join(noAdjacentDup(s)))
# This code is contributed by Anant Agarwal.
// C# program to print a string with
// no adjacent duplicates by doing
// minimum changes to original string
using 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 = "w3wiki";
// Function calling
Console.Write(noAdjacentDup(s));
}
}
/* This code is contributed by parashar */
<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 = "w3wiki";
document.write(noAdjacentDup(s));
</script>
<?php
// PHP program to print a
// string with no adjacent
// duplicates by doing minimum
// changes to original string
// Function to print
// simple string
function 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 = "w3wiki";
echo (noAdjacentDup($s));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Output
geaksforgeaks
Time Complexity: O(N2)
Auxiliary Space: O(1)
Print a Closest String with No Adjacent Duplicates in O(n) time:
Iterates through the string, and whenever it encounters adjacent characters that are the same, it replaces the current character with ‘a’ and continues iterating until the current character is different from both its left and right neighbors.
To efficiently print a string with no adjacent duplicates while making the smallest number of changes, we can adopt a greedy approach. Here’s why this approach is preferred:
- Start by traversing the string from left to right. Whenever we encounter two adjacent characters that are the same, we replace the current character with ‘a’ and then iterate until the current character is different from both its left and right neighbors.
- By focusing on each pair of adjacent characters and ensuring that the current character is different from its neighbors, we minimize the number of changes needed to eliminate adjacent duplicates.
Below is the implementation of above approach:
#include <iostream>
#include <string>
using namespace std;
string closestStringNoDuplicates(string s)
{
char* chars = const_cast<char*>(s.c_str());
int n = s.length();
for (int i = 1; i < n; i++) {
if (chars[i] == chars[i - 1]) {
// Replace current character with 'a'
chars[i] = 'a';
// Iterate until the current character is
// different from both neighbors
while (chars[i] == chars[i - 1]
|| (i + 1 < n
&& chars[i] == chars[i + 1])) {
// Increment character to ensure no
// adjacent duplicates
chars[i]++;
}
i++;
}
}
return string(chars);
}
int main()
{
string s = "w3wiki";
cout << closestStringNoDuplicates(s) << endl;
return 0;
}
// This code is contributed by Shivam
public class ClosestStringNoDuplicates {
public static String closestStringNoDuplicates(String s)
{
char[] chars = s.toCharArray();
int n = chars.length;
for (int i = 1; i < n; i++) {
if (chars[i] == chars[i - 1]) {
// Replace current character with 'a'
chars[i] = 'a';
// Iterate until the current character is
// different from both neighbors
while (chars[i] == chars[i - 1]
|| (i + 1 < n
&& chars[i] == chars[i + 1])) {
// Increment character to ensure no
// adjacent duplicates
chars[i]++;
}
i++;
}
}
return new String(chars);
}
public static void main(String[] args)
{
String s = "w3wiki";
System.out.println(closestStringNoDuplicates(s));
}
}
// This code is contributed by Shivam Gupta
def closest_string_no_duplicates(s):
n = len(s)
for i in range(1, n):
if s[i] == s[i - 1]:
# Replace current character with 'a'
s[i] = "a"
# Iterate until the current character is different from both neighbors
while s[i] == s[i - 1] or (i + 1 < n and s[i] == s[i + 1]):
# Increment character to ensure no adjacent duplicates
s[i] = chr(ord(s[i]) + 1)
i += 1
return "".join(s)
# Example usage:
s = list("w3wiki")
print(closest_string_no_duplicates(s))
// Function to find the closest string with no consecutive duplicates
function closestStringNoDuplicates(s) {
// Convert string to an array of characters
let chars = s.split('');
let n = s.length;
// Iterate through each character of the string
for (let i = 1; i < n; i++) {
// If the current character is the same as the previous one
if (chars[i] === chars[i - 1]) {
// Replace current character with 'a'
chars[i] = 'a';
// Iterate until the current character is different from both neighbors
while (chars[i] === chars[i - 1] || (i + 1 < n && chars[i] === chars[i + 1])) {
// Increment character to ensure no adjacent duplicates
chars[i] = String.fromCharCode(chars[i].charCodeAt(0) + 1);
}
i++; // Increment i to skip the next character since it's already handled
}
}
// Join the array of characters back into a string and return
return chars.join('');
}
// Main function
function main() {
let s = "w3wiki";
console.log(closestStringNoDuplicates(s)); // Output: "geksforheks"
}
// Call the main function to execute the example usage
main();
Output
geaksforgeaks
Time Complexity: O(N)
Auxiliary Space: O(1)