Encuentre la string presente en el medio de una secuencia lexicográficamente creciente de strings de S a T

Dadas dos strings S y T , siendo S lexicográficamente mayor que T , la tarea es generar una secuencia lexicográficamente creciente de strings comenzando desde S a T ( ambos inclusive ) e imprimir la string que está presente en el medio de la secuencia. 
Nota: siempre habrá un número impar de strings en la secuencia lexicográficamente creciente.

Ejemplo:

Entrada: N = 2, S = “az”, T = “bf”
Salida: “bc”
Explicación: La secuencia lexicográficamente creciente de strings es “az”, “ba”, “bb”, “bc”, “bd” , “ser”, “bf”. La string en el medio es «bc».

Entrada: S = “afogk”, T = “asdji”
Salida: “alvuw”

Enfoque:  siga los pasos a continuación para resolver el problema:

• Cada string se puede representar en base 26 en términos de números enteros entre [0, 26).
• Si las strings representan dos números enteros L y R , el resultado será (L + R)/2, que será el número del medio.
• Usando el concepto similar, las strings se pueden representar en términos de números de base 26
• Strings como “az” se pueden representar como (0 25) ₂₆ , “bf” se puede representar como (1 5) ₂₆ ; y “” se puede representar como() ₂₆
• Después de convertir las strings a sus respectivos números de base 26, obtenga su suma bit a bit .
• Agregue los bits iterando de derecha a izquierda y transfiera el resto a la siguiente posición.
• La suma de (0 25) ₂₆ y (1 5) ₂₆ será (2 4) ₂₆ .
• Tome la mitad del valor de cada posición e imprima el carácter correspondiente. Si la posición es impar, cambie la siguiente posición 26 caracteres.

Ilustración:

S = “afogk”, T = “asdji”
 

• Representación de 26 bases de S = [0, 5, 14, 6, 10]
• Representación de 26 bases de T = [0, 18, 3, 9, 8]
• Suma de strings S y T = [0, 23, 17, 15, 18]
• Representación de string intermedia de (S + T)/2 = [0, 11, 21, 20, 22]
• Entonces, cada carácter en la string será el a [i] th carácter de ‘a’ en 0 basado – indexación

 

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

// C++ Program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the string at
// the middle of lexicographically
// increasing sequence of strings from S to T
int printMiddleString(string S, string T, int N)
{
    // Stores the base 26 digits after addition
    vector<int> a1(N + 1);
 
    for (int i = 0; i < N; i++) {
        a1[i + 1] = S[i] - 'a' + T[i] - 'a';
    }
 
    // Iterete from right to left
    // and add carry to next position
    for (int i = N; i >= 1; i--) {
        a1[i - 1] += a1[i] / 26;
        a1[i] %= 26;
    }
 
    // Reduce the number to find the middle
    // string by dividing each position by 2
    for (int i = 0; i <= N; i++) {
 
        // If current value is odd,
        // carry 26 to the next index value
        if (a1[i] & 1) {
 
            if (i + 1 <= N) {
                a1[i + 1] += 26;
            }
        }
 
        a1[i] /= 2;
    }
 
    for (int i = 1; i <= N; i++) {
        cout << char(a1[i] + 'a');
    }
    return 0;
}
 
// Driver Code
int main()
{
    int N = 5;
    string S = "afogk";
    string T = "asdji";
    printMiddleString(S, T, N);
}

// Java Program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to print the string at
    // the middle of lexicographically
    // increasing sequence of strings from S to T
    static void printMiddleString(String S, String T, int N)
    {
        // Stores the base 26 digits after addition
        int[] a1 = new int[N + 1];
 
        for (int i = 0; i < N; i++) {
            a1[i + 1] = (int)S.charAt(i) - 97
                        + (int)T.charAt(i) - 97;
        }
 
        // Iterete from right to left
        // and add carry to next position
        for (int i = N; i >= 1; i--) {
            a1[i - 1] += (int)a1[i] / 26;
            a1[i] %= 26;
        }
 
        // Reduce the number to find the middle
        // string by dividing each position by 2
        for (int i = 0; i <= N; i++) {
 
            // If current value is odd,
            // carry 26 to the next index value
            if ((a1[i] & 1) != 0) {
 
                if (i + 1 <= N) {
                    a1[i + 1] += 26;
                }
            }
 
            a1[i] = (int)a1[i] / 2;
        }
 
        for (int i = 1; i <= N; i++) {
            System.out.print((char)(a1[i] + 97));
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        String S = "afogk";
        String T = "asdji";
        printMiddleString(S, T, N);
    }
}
 
// This code is contributed by ukasp.

# Python Program for the above approach
 
# Function to print the string at
# the middle of lexicographically
# increasing sequence of strings from S to T
def printMiddleString(S, T, N):
   
  # Stores the base 26 digits after addition
  a1 = [0] * (N + 1);
 
  for i in range(N):
    a1[i + 1] = ord(S[i]) - ord("a") + ord(T[i]) - ord("a");
   
 
  # Iterete from right to left
  # and add carry to next position
  for i in range(N, 1, -1):
    a1[i - 1] += a1[i] // 26;
    a1[i] %= 26;
   
 
  # Reduce the number to find the middle
  # string by dividing each position by 2
  for i in range(N+1):
    # If current value is odd,
    # carry 26 to the next index value
    if (a1[i] & 1):
      if (i + 1 <= N):
        a1[i + 1] += 26;
   
    a1[i] = a1[i] // 2;
   
  for i in range(1, N + 1):
    print(chr(a1[i] + ord("a")), end="");
   
  return 0;
 
# Driver Code
N = 5;
S = "afogk";
T = "asdji";
printMiddleString(S, T, N);
 
# This code is contributed by gfgking

// C# Program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to print the string at
// the middle of lexicographically
// increasing sequence of strings from S to T
static void printMiddleString(string S, string T, int N)
{
    // Stores the base 26 digits after addition
    int []a1 = new int[N + 1];
 
    for (int i = 0; i < N; i++) {
        a1[i + 1] = (int)S[i] - 97 + (int)T[i] - 97;
    }
 
    // Iterete from right to left
    // and add carry to next position
    for (int i = N; i >= 1; i--) {
        a1[i - 1] += (int)a1[i] / 26;
        a1[i] %= 26;
    }
 
    // Reduce the number to find the middle
    // string by dividing each position by 2
    for (int i = 0; i <= N; i++) {
 
        // If current value is odd,
        // carry 26 to the next index value
        if ((a1[i] & 1)!=0) {
 
            if (i + 1 <= N) {
                a1[i + 1] += 26;
            }
        }
 
        a1[i] = (int)a1[i]/2;
    }
 
    for (int i = 1; i <= N; i++) {
        Console.Write(Convert.ToChar(a1[i] + 'a'));
    }
     
}
 
// Driver Code
public static void Main()
{
    int N = 5;
    string S = "afogk";
    string T = "asdji";
    printMiddleString(S, T, N);
}
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript Program for the above approach
 
// Function to print the string at
// the middle of lexicographically
// increasing sequence of strings from S to T
function printMiddleString(S, T, N) {
  // Stores the base 26 digits after addition
  let a1 = new Array(N + 1);
 
  for (let i = 0; i < N; i++) {
    a1[i + 1] = S[i].charCodeAt(0) - "a".charCodeAt(0) + T[i].charCodeAt(0) - "a".charCodeAt(0);
  }
 
  // Iterete from right to left
  // and add carry to next position
  for (let i = N; i >= 1; i--) {
    a1[i - 1] += a1[i] / 26;
    a1[i] %= 26;
  }
 
  // Reduce the number to find the middle
  // string by dividing each position by 2
  for (let i = 0; i <= N; i++) {
    // If current value is odd,
    // carry 26 to the next index value
    if (a1[i] & 1) {
      if (i + 1 <= N) {
        a1[i + 1] += 26;
      }
    }
 
    a1[i] = Math.floor(a1[i] / 2);
  }
 
  for (let i = 1; i <= N; i++) {
    document.write(String.fromCharCode(a1[i] + "a".charCodeAt(0)));
  }
  return 0;
}
 
// Driver Code
let N = 5;
let S = "afogk";
let T = "asdji";
printMiddleString(S, T, N);
 
// This code is contributed by _saurabh_jaiswal.
</script>

alvuw

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