Измените данную строку так, чтобы нечетные и четные индексы были лексикографически наибольшими и наименьшими

Опубликовано: 21 Сентября, 2022

Для заданной строки S , состоящей из N строчных букв, задача состоит в том, чтобы изменить данную строку, заменив все символы символами, отличными от текущего символа, так, чтобы строка суффиксов, образованная из нечетных и четных индексов, была лексикографически наибольшей и наименьшей соответственно среди всех возможных. модификации строки S .

Примеры:

Input: S = “giad”
Output: azbz
Explanation:
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

Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы заменить все символы нечетных индексов на символ «z», а если символ «z» присутствует, то заменить его на «y» . Точно так же замените все символы четных индексов символом «a», а если символ «a» присутствует, замените его на «b» . После вышеуказанных изменений выведите строку S в качестве результирующей строки.

Ниже приведена реализация вышеуказанного подхода:

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>

Временная сложность: O(N)
Вспомогательное пространство: O(1)

Mathematical

Измените данную строку так, чтобы нечетные и четные индексы были лексикографически наибольшими и наименьшими

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ