Given a string str consisting of lowercase English alphabets, the task is to convert the string so that it holds only distinct characters. Any character of the string can be replaced by any other lowercase character (the number of replacements must be minimum). Print the modified string.
Examples:
Input: str = “neveropen”
Output: abcdhforgieks
Input: str = “bbcaacgkkk”
Output: dbefacghik
Approach: If the length of the string > 26 then it won’t be possible for the string to have all distinct characters.
Else, count the occurrence for each of the character of the string and for the characters that appear more than once, replace them with some character that hasn’t appeared in the string yet. Print the modified string in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std; // Function to return the index of the character // that has 0 occurrence starting from index i int nextZero(int i, int occurrences[]) { while (i < 26) { // If current character has 0 occurrence if (occurrences[i] == 0) return i; i++; } // If no character has 0 occurrence return -1; } // Function to return the modified string // which consists of distinct characters string getModifiedString(string str) { int n = str.length(); // String cannot consist of // all distinct characters if (n > 26) return "-1"; string ch = str; int i, occurrences[26] = {0}; // Count the occurrences for // each of the character for (i = 0; i < n; i++) occurrences[ch[i] - 'a']++; // Index for the first character // that hasn't appeared in the string int index = nextZero(0, occurrences); for (i = 0; i < n; i++) { // If current character appeared more // than once then it has to be replaced // with some character that // hasn't occurred yet if (occurrences[ch[i] - 'a'] > 1) { // Decrement current character's occurrence by 1 occurrences[ch[i] - 'a']--; // Replace the character ch[i] = (char)('a' + index); // Update the new character's occurrence // This step can also be skipped as // we'll never encounter this character // in the string because it has // been added just now occurrences[index] = 1; // Find the next character that hasn't occurred yet index = nextZero(index + 1, occurrences); } } cout << ch << endl; } // Driver code int main() { string str = "neveropen"; getModifiedString(str); } // This code is contributed by Arnab Kundu |
Java
// Java implementation of the approachclass GFG { // Function to return the index of the character // that has 0 occurrence starting from index i static int nextZero(int i, int occurrences[]) { while (i < occurrences.length) { // If current character has 0 occurrence if (occurrences[i] == 0) return i; i++; } // If no character has 0 occurrence return -1; } // Function to return the modified string // which consists of distinct characters static String getModifiedString(String str) { int n = str.length(); // String cannot consist of all distinct characters if (n > 26) return "-1"; char ch[] = str.toCharArray(); int i, occurrences[] = new int[26]; // Count the occurrences for each of the character for (i = 0; i < n; i++) occurrences[ch[i] - 'a']++; // Index for the first character // that hasn't appeared in the string int index = nextZero(0, occurrences); for (i = 0; i < n; i++) { // If current character appeared more than once then // it has to be replaced with some character // that hasn't occurred yet if (occurrences[ch[i] - 'a'] > 1) { // Decrement current character's occurrence by 1 occurrences[ch[i] - 'a']--; // Replace the character ch[i] = (char)('a' + index); // Update the new character's occurrence // This step can also be skipped as we'll never encounter // this character in the string because // it has been added just now occurrences[index] = 1; // Find the next character that hasn't occurred yet index = nextZero(index + 1, occurrences); } } // Return the modified string return String.valueOf(ch); } // Driver code public static void main(String arr[]) { String str = "neveropen"; System.out.print(getModifiedString(str)); }} |
Python3
# Python3 implementation of the approach# Function to return the index of the character# that has 0 occurrence starting from index idef nextZero(i, occurrences): while i < 26: # If current character has 0 occurrence if occurrences[i] == 0: return i i += 1 # If no character has 0 occurrence return -1# Function to return the modified string# which consists of distinct charactersdef getModifiedString(str): n = len(str) # String cannot consist of # all distinct characters if n > 26: return "-1" ch = str ch = list(ch) occurrences = [0] * 26 # Count the occurrences for # each of the character for i in range(n): occurrences[ord(ch[i]) - ord('a')] += 1 # Index for the first character # that hasn't appeared in the string index = nextZero(0, occurrences) for i in range(n): # If current character appeared more # than once then it has to be replaced # with some character that # hasn't occurred yet if occurrences[ord(ch[i]) - ord('a')] > 1: # Decrement current character's occurrence by 1 occurrences[ord(ch[i]) - ord('a')] -= 1 # Replace the character ch[i] = chr(ord('a') + index) # Update the new character's occurrence # This step can also be skipped as # we'll never encounter this character # in the string because it has # been added just now occurrences[index] = 1 # Find the next character # that hasn't occurred yet index = nextZero(index + 1, occurrences) ch = ''.join(ch) print(ch)# Driver codeif __name__ == "__main__": str = "neveropen" getModifiedString(str)# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the approach using System;class GFG { // Function to return the index of the character // that has 0 occurrence starting from index i static int nextZero(int i, int []occurrences) { while (i < occurrences.Length) { // If current character has 0 occurrence if (occurrences[i] == 0) return i; i++; } // If no character has 0 occurrence return -1; } // Function to return the modified string // which consists of distinct characters static string getModifiedString(string str) { int n = str.Length ; // String cannot consist of all distinct characters if (n > 26) return "-1"; char []ch = str.ToCharArray(); int []occurrences = new int[26]; int i ; // Count the occurrences for each of the character for (i = 0; i < n; i++) occurrences[ch[i] - 'a']++; // Index for the first character // that hasn't appeared in the string int index = nextZero(0, occurrences); for (i = 0; i < n; i++) { // If current character appeared more than // once then it has to be replaced with some // character that hasn't occurred yet if (occurrences[ch[i] - 'a'] > 1) { // Decrement current character's occurrence by 1 occurrences[ch[i] - 'a']--; // Replace the character ch[i] = (char)('a' + index); // Update the new character's occurrence // This step can also be skipped // as we'll never encounter // this character in the string because // it has been added just now occurrences[index] = 1; // Find the next character that hasn't occurred yet index = nextZero(index + 1, occurrences); } } string s = new string(ch) ; // Return the modified string return s ; } // Driver code public static void Main() { string str = "neveropen"; Console.WriteLine(getModifiedString(str)); } } // This code is contributed by Ryuga |
Javascript
<script> // Javascript implementation of the approach // Function to return the index of the character // that has 0 occurrence starting from index i function nextZero(i, occurrences) { while (i < occurrences.length) { // If current character has 0 occurrence if (occurrences[i] == 0) return i; i++; } // If no character has 0 occurrence return -1; } // Function to return the modified string // which consists of distinct characters function getModifiedString(str) { let n = str.length ; // String cannot consist of all distinct characters if (n > 26) return "-1"; let ch = str.split(''); let occurrences = new Array(26); occurrences.fill(0); let i ; // Count the occurrences for each of the character for (i = 0; i < n; i++) occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()]++; // Index for the first character // that hasn't appeared in the string let index = nextZero(0, occurrences); for (i = 0; i < n; i++) { // If current character appeared more than // once then it has to be replaced with some // character that hasn't occurred yet if (occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()] > 1) { // Decrement current character's occurrence by 1 occurrences[ch[i].charCodeAt() - 'a'.charCodeAt()]--; // Replace the character ch[i] = String.fromCharCode('a'.charCodeAt() + index); // Update the new character's occurrence // This step can also be skipped // as we'll never encounter // this character in the string because // it has been added just now occurrences[index] = 1; // Find the next character that hasn't occurred yet index = nextZero(index + 1, occurrences); } } let s = ch.join(""); // Return the modified string return s ; } let str = "neveropen"; document.write(getModifiedString(str)); // This code is contributed by vaibhavrabadiya117.</script> |
Output:
abcdhforgieks
Time Complexity :- O(N),where N is the length of the string.
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!
