Lexicographically largest string possible by at most K replacements
Given a string S of length N, consisting of lowercase alphabets, the task is to find the lexicographically longest string that can be obtained by replacing at most K characters from the given string.
Examples:
Input: S = “dbza”, K = 1
Output: zbza
Explanation: Replace S[0] (= ‘d’) with ‘z’ to obtain the lexicographically largest string.Input: S = “zzzz”, K = 2
Output: zzzz
Approach: The given problem can be solved by using the Greedy Approach. The idea is to traverse the array from left to right and replace all the non z characters with z. Follow the steps below to solve the problem:
- Run a loop for i = 0 to the length of the string:
- If the current character is not equal to z, and K is not equal to 0:
- Then, replace the current character with z.
- K = K – 1.
- If the current character is not equal to z, and K is not equal to 0:
- Finally, return the modified string.
Below is the implementation of the above approach:
C++
// C++ implementation of // the above approach #include <bits/stdc++.h> using namespace std; string largestString(string s, int k) { // Traverse each element of the string for ( int i = 0; i < s.size(); i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s[i] = 'z' ; k--; } } // Return the modified string return s; } // Driver code int main() { string s = "dbza" ; int k = 1; cout << largestString(s, k) << endl; return 0; } |
Java
// Java implementation of the above approach class GFG{ static String largestString(String s, int k) { // Traverse each element of the string for ( int i = 0 ; i < s.length(); i++) { // If the current character // can be replaced with 'z' if (s.charAt(i) != 'z' && k > 0 ) { s = s.replace(s.charAt(i), 'z' ); k--; } } // Return the modified string return s; } // Driver code public static void main(String args[]) { String s = "dbza" ; int k = 1 ; System.out.println(largestString(s, k)); } } // This code is contributed by SoumikMondal |
Python3
# Python3 implementation of # the above approach def largestString(s, k): # Traverse each element of the string for i in range ( len (s)): # If the current character # can be replaced with 'z' if (s[i] ! = 'z' and k > 0 ): s[i] = 'z' k - = 1 # Return the modified string return "".join(s) # Driver code if __name__ = = '__main__' : s = "dbza" k = 1 print (largestString([i for i in s], k)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of // the above approach using System; using System.Collections.Generic; class GFG{ static string largestString( string s, int k) { // Traverse each element of the string for ( int i = 0; i < s.Length; i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s = s.Replace(s[i], 'z' ); k--; } } // Return the modified string return s; } // Driver code public static void Main() { string s = "dbza" ; int k = 1; Console.Write(largestString(s, k)); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // JavaScript implementation of // the above approach function largestString(s, k) { // Traverse each element of the string for (let i = 0; i < s.length; i++) { // If the current character // can be replaced with 'z' if (s[i] != 'z' && k > 0) { s = s.substring(0, i) + 'z' + s.substring(i + 1); k--; } } // Return the modified string return s; } // Driver code var s = "dbza" ; var k = 1; document.write(largestString(s, k)); // This code is contributed by Potta Lokesh </script> |
Output:
zbza
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us