Учитывая строку и целое число k, найдите k-ю подстроку, когда все подстроки отсортированы в соответствии с заданным условием

Опубликовано: 14 Января, 2022

Для данной строки 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; 
 &

РЕКОМЕНДУЕМЫЕ СТАТЬИ