Given two strings S and T, S being lexicographically greater than T, the task is to generate a lexicographically increasing sequence of strings starting from S to T ( both inclusive ) and print the string that is present at the middle of the sequence.
Note: There will always be an odd number of strings in the lexicographically increasing sequence.
Example:
Input: N = 2, S = “az”, T = “bf”
Output: “bc”
Explanation: The lexicographically increasing sequence of strings is “az”, “ba”, “bb”, “bc”, “bd”, “be”, “bf”. The string at the middle is “bc”.Input: S = “afogk”, T = “asdji”
Output: “alvuw”
Approach: Follow the steps below to solve the problem:
- Every string can be represented in base 26 in terms of integers between [0, 26).
- If the strings represented two integers L and R, then the result will be (L + R)/2 which will be the middle number.
- Using the similar concept, the strings can be represented in terms of base 26 numbers
- Strings such as “az” can be represented as (0 25)26, “bf” can be represented as (1 5)26; and “” can be represented as ()26
- After converting the strings to their respective base 26 numbers, obtain their bitwise summation.
- Add the bits iterating from right to left and carry over the remainder to the next position.
- The addition of (0 25)26 and (1 5)26 will be (2 4)26.
- Take the middle of every position’s value and print the corresponding character. If the position is odd, then shift the next position by 26 characters.
Illustration:
S = “afogk”, T = “asdji”
- 26 base representation of S = [0, 5, 14, 6, 10]
- 26 base representation of T = [0, 18, 3, 9, 8]
- Addition of strings S and T = [0, 23, 17, 15, 18]
- Middle string representation of (S + T)/2 = [0, 11, 21, 20, 22]
- So each character in string will be the a[i] th character from ‘a’ in 0 based – indexing
Below is the implementation of the above approach:
C++
// 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 Tint 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'; } // Iterate 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 Codeint main(){ int N = 5; string S = "afogk"; string T = "asdji"; printMiddleString(S, T, N);} |
Java
// Java Program for the above approachimport 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; } // Iterate 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. |
Python3
# Python Program for the above approach# Function to print the string at# the middle of lexicographically# increasing sequence of strings from S to Tdef 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"); # Iterate 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 CodeN = 5;S = "afogk";T = "asdji";printMiddleString(S, T, N);# This code is contributed by gfgking |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to print the string at// the middle of lexicographically// increasing sequence of strings from S to Tstatic 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; } // Iterate 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 Codepublic static void Main(){ int N = 5; string S = "afogk"; string T = "asdji"; printMiddleString(S, T, N);}}// This code is contributed by ipg2016107. |
Javascript
<script>// Javascript Program for the above approach// Function to print the string at// the middle of lexicographically// increasing sequence of strings from S to Tfunction 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); } // Iterate 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 Codelet N = 5;let S = "afogk";let T = "asdji";printMiddleString(S, T, N);// This code is contributed by _saurabh_jaiswal.</script> |
Output:
alvuw
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
