# Modify given string such that odd and even indices is lexicographically largest and smallest

Given a string **S **consisting of **N** lowercase alphabets, the task is to modify the given string by replacing all the characters with characters other than the current character such that the suffix string formed from **odd** and **even** indices is lexicographically largest and smallest respectively among all possible modifications of the string **S**.

**Examples:**

Input:S = “giad”Output:azbzExplanation:

Modify the given string S to “azbz”.

Now the suffixes starting at odd indices {zbz, z} are lexicographically largest among all possible replacements of characters.

And all the suffixes starting at even indices {azbz, bz} are lexicographically smallest among all possible replacements of characters.

Input:S = “ewdwnk”Output:azazaz

**Approach:** The given problem can be solved by using the Greedy Approach. The idea is to replace all the odd indices characters with the character **‘z’** and if the character **‘z’** is present then replace it with **‘y’**. Similarly, replace all the even indices characters with the character **‘a’** and if the character **‘a’** is present then replace it with **‘b’**. After the above modifications, print the string **S** as the resultant string formed.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to modify the given string` `// satisfying the given criteria` `string performOperation(string S, ` `int` `N)` `{` ` ` `// Traverse the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// If i is even` ` ` `if` `(i % 2 == 0) {` ` ` `// If the S[i] is 'a', then` ` ` `// change S[i] to 'b'` ` ` `if` `(S[i] == ` `'a'` `) {` ` ` `S[i] = ` `'b'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'a'` ` ` `else` `{` ` ` `S[i] = ` `'a'` `;` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `// If S[i] is 'z', then` ` ` `// change S[i] to 'y'` ` ` `if` `(S[i] == ` `'z'` `) {` ` ` `S[i] = ` `'y'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'z'` ` ` `else` `{` ` ` `S[i] = ` `'z'` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the result` ` ` `return` `S;` `}` `// Driver Code` `int` `main()` `{` ` ` `string S = ` `"giad"` `;` ` ` `int` `N = S.size();` ` ` `cout << performOperation(S, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Function to modify the given String` `// satisfying the given criteria` `static` `String performOperation(` `char` `[] S, ` `int` `N)` `{` ` ` ` ` `// Traverse the String S` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++) {` ` ` `// If i is even` ` ` `if` `(i % ` `2` `== ` `0` `) {` ` ` `// If the S[i] is 'a', then` ` ` `// change S[i] to 'b'` ` ` `if` `(S[i] == ` `'a'` `) {` ` ` `S[i] = ` `'b'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'a'` ` ` `else` `{` ` ` `S[i] = ` `'a'` `;` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `// If S[i] is 'z', then` ` ` `// change S[i] to 'y'` ` ` `if` `(S[i] == ` `'z'` `) {` ` ` `S[i] = ` `'y'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'z'` ` ` `else` `{` ` ` `S[i] = ` `'z'` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the result` ` ` `return` `String.valueOf(S);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `String S = ` `"giad"` `;` ` ` `int` `N = S.length();` ` ` `System.out.print(performOperation(S.toCharArray(), N));` `}` `}` `// This code is contributed by shikhasingrajput` |

## Python3

`# python program for the above approach` `# Function to modify the given string` `# satisfying the given criteria` `def` `performOperation(S, N):` ` ` ` ` `# Traverse the string S` ` ` `# we cannot directly change string` ` ` `# because it is immutable` ` ` `# so change of list of char` ` ` `S ` `=` `list` `(S)` ` ` `for` `i ` `in` `range` `(` `0` `, N):` ` ` `# If i is even` ` ` `if` `(i ` `%` `2` `=` `=` `0` `):` ` ` `# If the S[i] is 'a', then` ` ` `# change S[i] to 'b'` ` ` `if` `(S[i] ` `=` `=` `'a'` `):` ` ` `S[i] ` `=` `'b'` ` ` `# Otherwise, change S[i]` ` ` `# to 'a'` ` ` `else` `:` ` ` `S[i] ` `=` `'a'` ` ` `else` `:` ` ` `# If S[i] is 'z', then` ` ` `# change S[i] to 'y'` ` ` `if` `(S[i] ` `=` `=` `'z'` `):` ` ` `S[i] ` `=` `'y'` ` ` `# Otherwise, change S[i]` ` ` `# to 'z'` ` ` `else` `:` ` ` `S[i] ` `=` `'z'` ` ` `# Return the result` ` ` `# join the list of char` ` ` `return` `"".join(S)` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `S ` `=` `"giad"` ` ` `N ` `=` `len` `(S)` ` ` `print` `(performOperation(S, N))` ` ` ` ` `# This code is contributed by rakeshsahni` |

## C#

`// C# program for the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` `// Function to modify the given string` `// satisfying the given criteria` `static` `string` `performOperation(` `string` `S, ` `int` `N)` `{` ` ` ` ` `// Traverse the string S` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `// If i is even` ` ` `if` `(i % 2 == 0) {` ` ` `// If the S[i] is 'a', then` ` ` `// change S[i] to 'b'` ` ` `if` `(S[i] == ` `'a'` `) {` ` ` `S = S.Substring(0, i) + ` `'b'` `+ S.Substring(i + 1);` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'a'` ` ` `else` `{` ` ` `S = S.Substring(0, i) + ` `'a'` `+ S.Substring(i + 1);` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `// If S[i] is 'z', then` ` ` `// change S[i] to 'y'` ` ` `if` `(S[i] == ` `'z'` `) {` ` ` `S = S.Substring(0, i) + ` `'y'` `+ S.Substring(i + 1);` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'z'` ` ` `else` `{` ` ` `S = S.Substring(0, i) + ` `'z'` `+ S.Substring(i + 1);` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the result` ` ` `return` `S;` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `string` `S = ` `"giad"` `;` ` ` `int` `N = S.Length;` ` ` `Console.Write(performOperation(S, N));` `}` `}` `// This code is contributed by ipg2016107.` |

## Javascript

`<script>` `// JavaScript program for the above approach` `// Function to modify the given string` `// satisfying the given criteria` `function` `performOperation(S, N)` `{` ` ` `// Traverse the string S` ` ` `for` `(` `var` `i = 0; i < N; i++) {` ` ` `// If i is even` ` ` `if` `(i % 2 == 0) {` ` ` `// If the S[i] is 'a', then` ` ` `// change S[i] to 'b'` ` ` `if` `(S.charAt(i) == ` `'a'` `) {` ` ` `S[i] = ` `'b'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'a'` ` ` `else` `{` ` ` `S[i]= ` `'a'` `;` ` ` `}` ` ` `}` ` ` `else` `{` ` ` `// If S[i] is 'z', then` ` ` `// change S[i] to 'y'` ` ` `if` `(S.charAt(i) == ` `'z'` `) {` ` ` `S.charAt(i) = ` `'y'` `;` ` ` `}` ` ` `// Otherwise, change S[i]` ` ` `// to 'z'` ` ` `else` `{` ` ` `S[i] = ` `'z'` `;` ` ` `}` ` ` `}` ` ` `}` ` ` `// Return the result` ` ` `return` `S;` `}` `// Driver Code` ` ` `var` `S = ` `"giad"` `;` ` ` `var` `N = S.length;` ` ` `document.write(performOperation(S, N));` ` ` `// This code is contributed by shivanisinghss2110` `</script>` |

**Output:**

azbz

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.