Учитывая строку и целое число k, найдите k-ю подстроку, когда все подстроки отсортированы в соответствии с заданным условием
Для данной строки str ее подстроки формируются таким образом, что все подстроки, начинающиеся с первого символа строки, будут появляться первыми в отсортированном порядке их длины, за которыми следуют все подстроки, начиная со второго. символ строки в отсортированном порядке их длины и так далее.
Например, для строки abc ее подстроки в требуемом порядке: a , ab , abc , b , bc и c .
Теперь, когда задано целое число k , задача состоит в том, чтобы найти k-ю подстроку в нужном порядке.
Примеры:
Input: str = abc, k = 4
Output: b
The required order is “a”, “ab”, “abc”, “b”, “bc” and “c”Input: str = abc, k = 9
Output: -1
Only 6 sub-strings are possible.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея заключается в использовании бинарного поиска. Подстроки массив будет использоваться для хранения количества суб-строк , начиная с символа + Ith подстроку [я - 1]. Теперь, используя двоичный поиск по подстроке массива, найдите начальный индекс требуемой подстроки, а затем найдите конечный индекс для той же подстроки с end = length_of_string - (substring [start] - k).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to prints kth sub-string void Printksubstring(string str, int n, int k) { // Total sub-strings possible int total = (n * (n + 1)) / 2; // If k is greater than total // number of sub-strings if (k > total) { printf ( "-1
" ); return ; } // To store number of sub-strings starting // with ith character of the string int substring[n + 1]; substring[0] = 0; // Compute the values int temp = n; for ( int i = 1; i <= n; i++) { // substring[i - 1] is added // to store the cumulative sum substring[i] = substring[i - 1] + temp; temp--; } // Binary search to find the starting index // of the kth sub-string int l = 1; int h = n; int start = 0; while (l <= h) { int m = (l + h) / 2; if (substring[m] > k) { start = m; h = m - 1; } else if (substring[m] < k) l = m + 1; else { start = m; break ; } } // To store the ending index of // the kth sub-string int end = n - (substring[start] - k); // Print the sub-string for ( int i = start - 1; i < end; i++) cout << str[i]; } // Driver code int main() { string str = "abc" ; int k = 4; int n = str.length(); Printksubstring(str, n, k); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to prints kth sub-string static void Printksubstring(String str, int n, int k) { // Total sub-strings possible int total = (n * (n + 1 )) / 2 ; // If k is greater than total // number of sub-strings if (k > total) { System.out.printf( "-1
" ); return ; } // To store number of sub-strings starting // with ith character of the string int substring[] = new int [n + 1 ]; substring[ 0 ] = 0 ; // Compute the values int temp = n; for ( int i = 1 ; i <= n; i++) { // substring[i - 1] is added // to store the cumulative sum substring[i] = substring[i - 1 ] + temp; temp--; } // Binary search to find the starting index // of the kth sub-string int l = 1 ; int h = n; int start = 0 ; while (l <= h) { int m = (l + h) / 2 ; if (substring[m] > k) { start = m; h = m - 1 ; } else if (substring[m] < k) { l = m + 1 ; } else { start = m; break ; } } // To store the ending index of // the kth sub-string int end = n - (substring[start] - k); // Print the sub-string for ( int i = start - 1 ; i < end; i++) { System.out.print(str.charAt(i)); } } // Driver code public static void main(String[] args) { String str = "abc" ; int k = 4 ; int n = str.length(); Printksubstring(str, n, k); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to prints kth sub-string def Printksubstring(str1, n, k): # Total sub-strings possible total = int ((n * (n + 1 )) / 2 ) # If k is greater than total # number of sub-strings if (k > total): print ( "-1" ) return # To store number of sub-strings starting # with ith character of the string substring = [ 0 for i in range (n + 1 )] substring[ 0 ] = 0 # Compute the values temp = n for i in range ( 1 , n + 1 , 1 ): # substring[i - 1] is added # to store the cumulative sum substring[i] = substring[i - 1 ] + temp temp - = 1 # Binary search to find the starting index # of the kth sub-string l = 1 h = n start = 0 while (l < = h): m = int ((l + h) / 2 ) if (substring[m] > k): start = m h = m - 1 elif (substring[m] < k): l = m + 1 else : start = m break # To store the ending index of # the kth sub-string end = n - (substring[start] - k) # Print the sub-string for i in range (start - 1 , end): print (str1[i], end = "") # Driver code if __name__ = = "__main__" : str1 = "abc" k = 4 n = len (str1) Printksubstring(str1, n, k) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to prints kth sub-string static void Printksubstring(String str, int n, int k) { // Total sub-strings possible int total = (n * (n + 1)) / 2; // If k is greater than total // number of sub-strings if (k > total) { Console.Write( "-1
" ); return ; } // To store number of sub-strings starting // with ith character of the string int []substring = new int [n + 1]; substring[0] = 0; // Compute the values int temp = n; for ( int i = 1; i <= n; i++) { // substring[i - 1] is added // to store the cumulative sum substring[i] = substring[i - 1] + temp; temp--; } // Binary search to find the starting index // of the kth sub-string int l = 1; int h = n; int start = 0; while (l <= h) { int m = (l + h) / 2; if (substring[m] > k) { start = m; h = m - 1; } else if (substring[m] < k) { l = m + 1; } else { start = m; break ; } } // To store the ending index of // the kth sub-string int end = n - (substring[start] - k); // Print the sub-string for ( int i = start - 1; i < end; i++) { Console.Write(str[i]); } } // Driver code public static void Main(String[] args) { String str = "abc" ; int k = 4; int n = str.Length; Printksubstring(str, n, k); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP implementation of the approach // Function to prints kth sub-string function Printksubstring( $str , $n , $k ) { // Total sub-strings possible $total = floor (( $n * ( $n + 1)) / 2); // If k is greater than total // number of sub-strings if ( $k > $total ) { printf( "-1
" ); return ; } // To store number of sub-strings starting // with ith character of the string $substring = array (); $substring [0] = 0; // Compute the values $temp = $n ; for ( $i = 1; $i <= $n ; $i ++) { // substring[i - 1] is added // to store the cumulative sum $substring [ $i ] = $substring [ $i - 1] + $temp ; $temp --; } // Binary search to find the starting index // of the kth sub-string $l = 1; &
РЕКОМЕНДУЕМЫЕ СТАТЬИ |