Given a string s written in median form, change it back to the original string. The median letter in a string is the letter that is in the middle of the string. If the string’s length is even, the median letter is the left of the two middle letters. The given string is formed by writing down the median letter of the word, then deleting it and repeating the process until there are no letters left.
Examples:
Input: eekgs Output: neveropen Explanation: in the original string “neveropen” can be written in median form by picking up e first then, again e, then k then g and at the end s. As these are the median when the median letter is picked and deleted. Input: abc Output: bac Explanation: median of bac is a, then median of bc is b, then median of c is c.
To find the answer we can iterate through the given encoded string from left to right and add each letter in the answer string, one letter to the beginning, next letter to the end, next letter to begin, and so on. If n is even then the first letter must be added to the beginning and the second letter to the end. In the other case, the first letter to the end, second to the beginning. We need to make it until we do not add all letters from the given string.
Note: For strings with even length, when we add the first character to begin and the second character to the end then the remaining string will always be of even length. The same is true for strings with odd lengths.
Given below is the implementation of the above approach
C++
// C++ program to decode a median string // to the original string #include <bits/stdc++.h> using namespace std; // function to calculate the median back string string decodeMedianString(string s) { // length of string int l = s.length(); // initialize a blank string string s1 = ""; // Flag to check if length is even or odd bool isEven = (l % 2 == 0)? true : false; // traverse from first to last for (int i = 0; i < l; i += 2) { // if len is even then add first character // to beginning of new string and second // character to end if (isEven) { s1 = s[i] + s1; s1 += s[i + 1]; } else { // if current length is odd and is // greater than 1 if (l - i > 1) { // add first character to end and // second character to beginning s1 += s[i]; s1 = s[i + 1] + s1; } else { // if length is 1, add character // to end s1 += s[i]; } } } return s1; } // driver program int main() { string s = "eekgs"; cout << decodeMedianString(s); return 0; } |
Java
// java program to decode a median // string to the original string public class GFG { // function to calculate the // median back string static String decodeMedianString(String s) { // length of string int l = s.length(); // initialize a blank string String s1 = ""; // Flag to check if length is // even or odd boolean isEven = (l % 2 == 0) ? true : false; // traverse from first to last for (int i = 0; i < l; i += 2) { // if len is even then add // first character to // beginning of new string // and second character to // end if (isEven) { s1 = s.charAt(i) + s1; s1 += s.charAt(i+1); } else { // if current length is // odd and is greater // than 1 if (l - i > 1) { // add first character // to end and second // character to // beginning s1 += s.charAt(i); s1 = s.charAt(i+1) + s1; } else { // if length is 1, // add character // to end s1 += s.charAt(i); } } } return s1; } // Driver code public static void main(String args[]) { String s = "eekgs"; System.out.println( decodeMedianString(s)); } } // This code is contributed by Sam007. |
Python3
# Python3 program to decode a median # string to the original string # function to calculate the median # back string def decodeMedianString(s): # length of string l = len(s) # initialize a blank string s1 = "" # Flag to check if length is # even or odd if(l % 2 == 0): isEven = True else: isEven = False # traverse from first to last for i in range(0, l, 2): # if len is even then add first # character to beginning of new # string and second character to end if (isEven): s1 = s[i] + s1 s1 += s[i + 1] else : # if current length is odd and # is greater than 1 if (l - i > 1): # add first character to end and # second character to beginning s1 += s[i] s1 = s[i + 1] + s1 else: # if length is 1, add character # to end s1 += s[i] return s1 # Driver Code if __name__ == '__main__': s = "eekgs" print(decodeMedianString(s)) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to decode a median // string to the original string using System; class GFG { // function to calculate the // median back string static string decodeMedianString(string s) { // length of string int l = s.Length; // initialize a blank string string s1 = ""; // Flag to check if length is // even or odd bool isEven = (l % 2 == 0) ? true : false; // traverse from first to last for (int i = 0; i < l; i += 2) { // if len is even then add // first character to // beginning of new string // and second character to // end if (isEven) { s1 = s[i] + s1; s1 += s[i + 1]; } else { // if current length is // odd and is greater // than 1 if (l - i > 1) { // add first character // to end and second // character to // beginning s1 += s[i]; s1 = s[i + 1] + s1; } else { // if length is 1, // add character // to end s1 += s[i]; } } } return s1; } // Driver code public static void Main () { string s = "eekgs"; Console.WriteLine( decodeMedianString(s)); } } // This code is contributed by Sam007. |
Javascript
<script> // javascript program to decode a median // string to the original string // function to calculate the // median back string function decodeMedianString( s) { // length of string var l = s.length; // initialize a blank string var s1 = ""; // Flag to check if length is // even or odd var isEven = (l % 2 == 0) ? true : false; // traverse from first to last for (i = 0; i < l; i += 2) { // if len is even then add // first character to // beginning of new string // and second character to // end if (isEven) { s1 = s.charAt(i) + s1; s1 += s.charAt(i + 1); } else { // if current length is // odd and is greater // than 1 if (l - i > 1) { // add first character // to end and second // character to // beginning s1 += s.charAt(i); s1 = s.charAt(i + 1) + s1; } else { // if length is 1, // add character // to end s1 += s.charAt(i); } } } return s1; } // Driver code var s = "eekgs"; document.write(decodeMedianString(s)); // This code contributed by Rajput-Ji </script> |
neveropen
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
This article is contributed by Striver. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
