Given a string S containing letter and digit and an integer K where, and
. The task is to return the K-th letter of the new string S’.
The new string S’ is formed from old string S by following steps:
1. If the character read is a letter, that letter is added at end of S’.
2. If the character read is a digit, then entire string S’ repeatedly written d-1 more times in total.
Note: The new string is guaranteed to have less than 2^63 letters.
Examples:
Input: S = “neveropen2for2”, K = 15
Output: “e”
Explanation: The new string S’ = “neveropenneveropenneveropenfor”. The 15th letter is “e”.Input: S = “a2345”, K = 100
Output: “a”
Explanation: The new string S’=”a” repeated 120 times. The 100th letter is “a”.
Let us take a new string like S’ = “neveropenneveropenneveropenneveropenneveropen” and an index K = 22, then the answer at K = 22 is the same if K = 2.
In general, when a string is equal to some word with size length repeated some number of times (such as neveropen with size = 5 repeated 5 times), then the answer will be same for the index K as it is for the index K % size.
Using this insight and working backwards, we keep track of the size of the new string S’. Whenever the string S’ would equal some word repeated d times, we can reduce K to K % (lengthof(word)).
We first find the length of the new string S’. After, this we’ll work backwards, keeping track of size: the length of the new string after parsing symbols S[0], S[1], …, S[i].
If we see a digit S[i], it means the size of the new string after parsing S[0], S[1], …, S[i-1] will be (size / toInteger(S[i])). Otherwise, it will be size – 1.
Below is the implementation of above approach:
C++
// CPP implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to return the K-th letter from new String. string K_thletter(string S, int K) { int N = S.size(); long size = 0; // finding size = length of new string S' for ( int i = 0; i < N; ++i) { if ( isdigit (S[i])) size = size * (S[i] - '0' ); else size += 1; } // get the K-th letter for ( int i = N - 1; i >= 0; --i) { K %= size; if (K == 0 && isalpha (S[i])) return (string) "" + S[i]; if ( isdigit (S[i])) size = size / (S[i] - '0' ); else size -= 1; } return "" ; } // Driver program int main() { string S = "neveropen2for2" ; int K = 15; cout << K_thletter(S, K); return 0; } // This code is written by Sanjit_Prasad |
Java
// Java implementation of above approach class GFG { // Function to return the K-th letter from new String. static String K_thletter(String S, int K) { int N = S.length(); long size = 0 ; // finding size = length of new string S' for ( int i = 0 ; i < N; ++i) { if (Character.isDigit(S.charAt(i))) { size = size * (S.charAt(i) - '0' ); } else { size += 1 ; } } // get the K-th letter for ( int i = N - 1 ; i >= 0 ; --i) { K %= size; if (K == 0 && Character.isAlphabetic(S.charAt(i))) { return (String) "" + S.charAt(i); } if (Character.isDigit(S.charAt(i))) { size = size / (S.charAt(i) - '0' ); } else { size -= 1 ; } } return null ; } // Driver program public static void main(String[] args) { String S = "neveropen2for2" ; int K = 15 ; System.out.println(K_thletter(S, K)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of above approach # Function to return the K-th letter # from new String. def K_thletter(S, K): N = len (S) size = 0 # finding size = length of new string S' for i in range ( 0 , N): if S[i].isdigit(): size = size * int (S[i]) else : size + = 1 # get the K-th letter for i in range (N - 1 , - 1 , - 1 ): K % = size if K = = 0 and S[i].isalpha(): return S[i] if S[i].isdigit(): size = size / / int (S[i]) else : size - = 1 # Driver Code if __name__ = = "__main__" : S = "neveropen2for2" K = 15 print (K_thletter(S, K)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of the above approach using System; class GFG { // Function to return the K-th letter from new String. static String K_thletter(String S, int K) { int N = S.Length; long size = 0; // finding size = length of new string S' for ( int i = 0; i < N; ++i) { if ( char .IsDigit(S[i])) { size = size * (S[i] - '0' ); } else { size += 1; } } // get the K-th letter for ( int i = N - 1; i >= 0; --i) { K %= ( int )size; if (K == 0 && char .IsLetter(S[i])) { return (String) "" + S[i]; } if ( char .IsDigit(S[i])) { size = size / (S[i] - '0' ); } else { size -= 1; } } return null ; } // Driver code public static void Main(String[] args) { String S = "neveropen2for2" ; int K = 15; Console.WriteLine(K_thletter(S, K)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of above approach function isAlphaNumeric(str) { var code, i, len; for (i = 0, len = str.length; i < len; i++) { code = str.charCodeAt(i); if (!(code > 47 && code < 58) && // numeric (0-9) !(code > 64 && code < 91) && // upper alpha (A-Z) !(code > 96 && code < 123)) { // lower alpha (a-z) return false ; } } return true ; }; // Function to return the K-th letter from new String. function K_thletter(S, K) { var N = S.length; var size = 0; // finding size = length of new string S' for ( var i = 0; i < N; ++i) { if (Number.isInteger(parseInt(S[i]))) size = size * (S[i].charCodeAt(0) - '0 '.charCodeAt(0)); else size += 1; } // get the K-th letter for (var i = N - 1; i >= 0; --i) { K %= size; if (K == 0 && isAlphaNumeric(S[i])) return "" + S[i]; if (Number.isInteger(parseInt(S[i]))) size = size / (S[i].charCodeAt(0) - ' 0'.charCodeAt(0)); else size -= 1; } } // Driver program var S = "neveropen2for2" ; var K = 15; document.write( K_thletter(S, K)); // This code is contributed by imporrtantly. </script> |
Output:
e
Time Complexity: O(N), where N is the length of S.
Auxiliary Space: O(1) since constant space is being used
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!