HackerEarth The Substring Game! problem solution

In this HackerEarth The Substring Game! problem solution Let’s play the Substring Game.

This game has two characters: Sherlock and Watson. As usual, Watson wants to test the skills of Mr. Sherlock.

Watson gives Sherlock a string (let’s denote it by S). Watson calculates all the substrings of S in his favourite order.

According to the Watson’s favourite order, all the substrings starting from first character of the string will occur first in the sorted order of their length, followed by all the substrings starting from the second character of the string in the sorted order of their length, and so on.

HackerEarth The Substring Game! problem solution.

import java.util.*;

public class Sol {

    public static void main(String args[]) throws Exception {
        Scanner in = new Scanner(System.in);

        String S = in.next();

        int n = S.length();
        long arr[] = new long[n + 1];
        for(int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + (long)n;
            n--;
        }

        long len = S.length();
        long max_substrings_possible = (len * (len + 1L)) / 2L;

        int q = in.nextInt();

        while(q-- > 0) {
            long number = in.nextLong();

            if(number > max_substrings_possible)
                System.out.println("-1");

            else {

                int l = 0, r = arr.length - 1;
                int index_of_substring = 0, length_of_substring = 0;

                while(l < r) {
                    int mid = (l + r) / 2;

                    if(arr[mid] >= number)
                        r = mid;
                    else
                        l = mid + 1;
                }

                index_of_substring = l;

                length_of_substring = (int)(number - arr[index_of_substring - 1]);

                String ans = S.substring(index_of_substring - 1, index_of_substring - 1 + length_of_substring);

                System.out.println(ans);
            }
        }
    }
}

HackerEarth The Substring Game! problem solution.

Leave a Reply