Haz la string en AP cambiando un carácter

Dada una string S que consta de letras tales que sus valores ASCII siguen una progresión aritmética. La tarea es encontrar la letra y el índice de la letra que desobedece al AP. Además, reemplace esta letra con la apropiada e imprima la string.

Ejemplos: 

Entrada: S = “abcdffghijkl” 
Salida: 4 -> f 
abcdefghijkl 
Explicación: 
En la string S dada, cada carácter que tiene el índice i varía de su índice anterior i-1 en un carácter en la dirección de avance. 
Para i = 4, S[4] = ‘f’ y S[3] = ‘d’ mientras que S[i] debería haber sido ‘e’ por lo que habría obedecido al patrón. Por lo tanto, reemplace S[4] con ‘e’. Por lo tanto, la string S modificada es «abcdefghijkl».

Entrada: S = “aeimqux” 
Salida: 6 -> x 
aeimquy

Entrada: S = “beimquy” 
Salida: 0 -> b 
aeimquy

Entrada: S = “xyzac” 
Salida: 4 -> c 
xyzab 

Acercarse: 

1. Cree una array para almacenar los valores ASCII de los alfabetos de la a a la z .
2. Recorra la string S y encuentre la diferencia entre los valores ASCII de dos caracteres consecutivos de la string utilizando la array creada anteriormente y almacene estos valores en un conjunto.
3. Para cada valor del conjunto, digamos D , construya una string T cuyos caracteres tengan una diferencia común de D unidades en sus valores ASCII.
4. Cada vez que se construye una nueva string T , su carácter inicial debe ser el mismo que el carácter inicial de la string S dada .
5. Si la string T difiere de la string S en 1 carácter, entonces T es la string modificada requerida. Encuentre el único índice donde estas dos strings difieren. Imprime ese índice y su carácter correspondiente.
6. Si T difiere de S en más de 1 carácter, descarte la string T y vaya al paso 3.
7. Si ninguna de las strings reconstruidas difiere de la string original en 1 carácter, entonces el primer carácter de la string S es el que desobedece al AP.

Explicación del enfoque anterior usando un ejemplo: 
S = «abcdffghijkl» 
set = {0, 1, 2} 
String reconstruida considerando la diferencia fija como 0 es «aaaaaaaaaaaa». Esta string difiere de la string original en 11 posiciones y, por lo tanto, no es la string requerida. 
La string reconstruida considerando la diferencia fija como 1 es «abcdefghijkl». Esta string difiere de la string original en 1 posición y, por lo tanto, es la string requerida. El índice requerido donde se tiene que modificar el carácter es 4. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
 
// Function to modify the given
// string and find the index
// where modification is needed
void string_modify(string s)
{
 
    // Array to store the ASCII
    // values of alphabets
    char alphabets[26];
 
    int flag = 0, hold_i;
    char hold_l;
    int i;
 
    // loop to compute the ASCII
    // values of characters a-z
    for (i = 0; i < 26; i++) {
        alphabets[i] = i + 'a';
    }
 
    // Set to store all the
    // possible differences
    // between consecutive elements
    set<int> difference;
 
    string reconstruct = "";
 
    // Loop to find out the
    // differences between
    // consecutive elements
    // and storing them in the set
    for (int i = 1;
        i < s.size(); i++) {
        difference.insert(s[i] - s[i - 1]);
    }
 
    // Checks if any character of the
    // string disobeys the pattern
    if (difference.size() == 1) {
        cout << "No modifications required";
        return;
    }
 
    // Constructing the strings with
    // all possible values of consecutive
    // difference and comparing them
    // with starting string S.
    for (auto it = difference.begin();
        it != difference.end(); it++) {
 
        int index = s[0] - 'a';
        reconstruct = "";
        flag = 0;
 
        for (int i = 0;
            i < s.size()
            && flag <= 1;
            i++) {
 
            reconstruct += alphabets[index];
            index += *it;
 
            if (index < 0) {
                index += 26;
            }
 
            index %= 26;
            if (reconstruct[i] != s[i]) {
 
                flag++;
                hold_i = i;
                hold_l = s[i];
            }
        }
 
        if (flag == 1) {
 
            s[hold_i] = reconstruct[hold_i];
            break;
        }
    }
 
    if (flag > 1) {
        hold_i = 0;
        hold_l = s[0];
 
        int temp = (s[1] - 'a' - (s[2] - s[1])) % 26;
 
        if (temp < 0) {
            temp += 26;
        }
        s[0] = alphabets[temp];
    }
 
    cout << hold_i << " -> "
        << hold_l << endl
        << s << endl;
}
 
// Driver Code
int main()
{
    string s = "aeimqux";
    string_modify(s);
}

// Java program for the above problem
import java.util.*;
 
class GFG{
     
// Function to modify the given
// String and find the index
// where modification is needed
static void string_modify(char[] s)
{
 
    // Array to store the ASCII
    // values of alphabets
    char []alphabets = new char[26];
 
    int flag = 0, hold_i = 0;
    char hold_l = 0;
    int i;
     
    // loop to compute the ASCII
    // values of characters a-z
    for(i = 0; i < 26; i++)
    {
        alphabets[i] = (char)(i + 'a');
    }
     
    // Set to store all the
    // possible differences
    // between consecutive elements
    HashSet<Integer>difference = new HashSet<Integer>();
     
    String reconstruct = "";
     
    // Loop to find out the
    // differences between
    // consecutive elements
    // and storing them in the set
    for(i = 1; i < s.length; i++)
    {
        difference.add(s[i] - s[i - 1]);
    }
     
    // Checks if any character of the
    // String disobeys the pattern
    if (difference.size() == 1)
    {
        System.out.print("No modifications required");
        return;
    }
     
    // Constructing the Strings with
    // all possible values of consecutive
    // difference and comparing them
    // with starting String S.
    for(int it : difference)
    {
        int index = s[0] - 'a';
        reconstruct = "";
        flag = 0;
         
        for(i = 0; i < s.length && flag <= 1; i++)
        {
            reconstruct += alphabets[index];
            index += it;
 
            if (index < 0)
            {
                index += 26;
            }
            index %= 26;
             
            if (reconstruct.charAt(i) != s[i])
            {
                flag++;
                hold_i = i;
                hold_l = s[i];
            }
        }
        if (flag == 1)
        {
            s[hold_i] = reconstruct.charAt(hold_i);
            break;
        }
    }
    if (flag < 1)
    {
        hold_i = 0;
        hold_l = s[0];
         
        int temp = (s[1] - 'a' - (s[2] - s[1])) % 26;
        if (temp < 0)
        {
            temp += 26;
        }
        s[0] = alphabets[temp];
    }
     
    System.out.print(hold_i + " -> " +
                     hold_l + "\n" +
                     String.valueOf(s) + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "aeimqux";
     
    string_modify(s.toCharArray());
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above problem
 
# Function to modify the given
# string and find the index
# where modification is needed
def string_modify(s):
 
    # Array to store the ASCII
    # values of alphabets
    alphabets = []
 
    flag, hold_i = 0, 0
    hold_l = s[0]
 
    # Loop to compute the ASCII
    # values of characters a-z
    for i in range(26):
        alphabets.append(chr(i + ord('a')))
 
    # Set to store all the
    # possible differences
    # between consecutive elements
    difference = set()
 
    reconstruct = ""
 
    # Loop to find out the
    # differences between
    # consecutive elements
    # and storing them in the set
    for i in range(1, len(s)):
        difference.add(ord(s[i]) -
                       ord(s[i - 1]))
 
    # Checks if any character of the
    # string disobeys the pattern
    if (len(difference) == 1):
        print("No modifications required")
        return
 
    # Constructing the strings with
    # all possible values of consecutive
    # difference and comparing them
    # with starting string S.
    for it in difference:
        index = ord(s[0]) - ord('a')
        reconstruct = ""
        flag = 0
        i = 0
         
        while ((i < len(s)) and (flag <= 1)):
            reconstruct += alphabets[index]
            index += it
 
            if (index < 0):
                index += 26
 
            index %= 26
            if (reconstruct[i] != s[i]):
                flag += 1
                hold_i = i
                hold_l = s[i]
     
            i += 1
 
        if (flag == 1):
            s[hold_i] = reconstruct[hold_i]
            break
 
    if (flag > 1):
        hold_i = 0
        hold_l = s[0]
 
        temp = (ord(s[1]) - ord('a') -
               (ord(s[2]) - ord(s[1]))) % 26
 
        if (temp < 0):
            temp += 26
         
        s[0] = alphabets[temp]
 
    print(hold_i, "->", hold_l)
    print("".join(s))
 
# Driver code
s = list("aeimqux")
 
string_modify(s)
 
# This code is contributed by divyeshrabadiya07

// C# program for the above problem
using System;
using System.Collections.Generic;
class GFG{
     
// Function to modify the given
// String and find the index
// where modification is needed
static void string_modify(char[] s)
{
 
    // Array to store the ASCII
    // values of alphabets
    char []alphabets = new char[26];
 
    int flag = 0, hold_i = 0;
    char hold_l = (char)0;
    int i;
     
    // loop to compute the ASCII
    // values of characters a-z
    for(i = 0; i < 26; i++)
    {
        alphabets[i] = (char)(i + 'a');
    }
     
    // Set to store all the
    // possible differences
    // between consecutive elements
    HashSet<int>difference = new HashSet<int>();
     
    String reconstruct = "";
     
    // Loop to find out the
    // differences between
    // consecutive elements
    // and storing them in the set
    for(i = 1; i < s.Length; i++)
    {
        difference.Add(s[i] - s[i - 1]);
    }
     
    // Checks if any character of the
    // String disobeys the pattern
    if (difference.Count == 1)
    {
        Console.Write("No modifications required");
        return;
    }
     
    // Constructing the Strings with
    // all possible values of consecutive
    // difference and comparing them
    // with starting String S.
    foreach(int it in difference)
    {
        int index = s[0] - 'a';
        reconstruct = "";
        flag = 0;
         
        for(i = 0; i < s.Length && flag <= 1; i++)
        {
            reconstruct += alphabets[index];
            index += it;
 
            if (index < 0)
            {
                index += 26;
            }
            index %= 26;
             
            if (reconstruct[i] != s[i])
            {
                flag++;
                hold_i = i;
                hold_l = s[i];
            }
        }
        if (flag == 1)
        {
            s[hold_i] = reconstruct[hold_i];
            break;
        }
    }
    if (flag < 1)
    {
        hold_i = 0;
        hold_l = s[0];
         
        int temp = (s[1] - 'a' - (s[2] - s[1])) % 26;
        if (temp < 0)
        {
            temp += 26;
        }
        s[0] = alphabets[temp];
    }
     
    Console.Write(hold_i + " -> " +
                     hold_l + "\n" +
                     String.Join("", s) + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
    String s = "aeimqux";
     
    string_modify(s.ToCharArray());
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program for the above problem
 
// Function to modify the given
// string and find the index
// where modification is needed
function string_modify(s)
{
 
    // Array to store the ASCII
    // values of alphabets
    var alphabets = Array(26).fill(0);
 
    var flag = 0, hold_i;
    var hold_l;
    var i;
 
    // loop to compute the ASCII
    // values of characters a-z
    for (i = 0; i < 26; i++) {
        alphabets[i] =
        String.fromCharCode(i + 'a'.charCodeAt(0));
    }
 
    // Set to store all the
    // possible differences
    // between consecutive elements
    var difference = new Set();
 
    var reconstruct = "";
 
    // Loop to find out the
    // differences between
    // consecutive elements
    // and storing them in the set
    for (var i = 1;
        i < s.length; i++) {
        difference.add(s[i].charCodeAt(0) -
        s[i - 1].charCodeAt(0));
    }
 
    // Checks if any character of the
    // string disobeys the pattern
    if (difference.size == 1) {
        document.write( "No modifications required");
        return;
    }
 
    // Constructing the strings with
    // all possible values of consecutive
    // difference and comparing them
    // with starting string S.
    [...difference].sort((a,b)=>a-b).forEach(it => {
       
        if(flag!=1)
        {
        var index = s[0].charCodeAt(0) - 'a'.charCodeAt(0);
        reconstruct = "";
        flag = 0;
 
        for (var i = 0;
            i < s.length
            && flag <= 1;
            i++) {
 
            reconstruct += alphabets[index];
            index += it;
 
            if (index < 0) {
                index += 26;
            }
 
            index %= 26;
            if (reconstruct[i] != s[i]) {
 
                flag++;
                hold_i = i;
                hold_l = s[i];
            }
        }
 
        if (flag == 1) {
 
            s[hold_i] = reconstruct[hold_i];
        }
        }
    });
 
    if (flag > 1) {
        hold_i = 0;
        hold_l = s[0];
 
        var temp = (s[1].charCodeAt(0) - 'a'.charCodeAt(0) -
        (s[2].charCodeAt(0) - s[1].charCodeAt(0))) % 26;
 
        if (temp < 0) {
            temp += 26;
        }
        s[0] = alphabets[temp];
    }
 
    document.write( hold_i + " -> "
        + hold_l + "<br>"
        + s.join('') + "<br>");
}
 
// Driver Code
var s = "aeimqux";
string_modify(s.split(''));
 
</script>

6 -> x
aeimquy

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)