Day 27 - Java - Strings 2

on

Nth Lexicographical Substrings

Problem Description:

Given a string S and two integers K and N, find the Nth lexicographically smallest and Nth lexicographically largest substrings of length K from the string S. If there are fewer than N substrings, return "INVALID" for that case.

Input Format:

  • The first line contains a string S consisting of lowercase English letters (1 ≤ |S| ≤ 1000).
  • The second line contains two integers K and N (1 ≤ K ≤ |S|, 1 ≤ N).

Output Format:

  • The first line should contain the Nth lexicographically smallest substring of length K, or "INVALID" if there are fewer than N substrings.
  • The second line should contain the Nth lexicographically largest substring of length K, or "INVALID" if there are fewer than N substrings.

Example Input 1:

enjoyjava
4 3

Example Output 1:

ava
toj

Example Input 2:

mahendrasinghdhoni
3 7

Example Output 2:

hdh
ing
Example Input 3:
chennaisuperkings
12 7

Example Output 3:
INVALID
INVALID

Explanation:

For the first example:

  • All possible substrings of length 3 are: [enjo, njoy, joyj, oyja, yjav, java]
  • Sorted substrings in lexicographical order: ava, [enjo, java, joyj, njoy, oyja, yjav]
    • 3rd smallest: joyj
    • 3rd largest: njoy

For the second example:

  • All possible substrings of length 4 are: [mah, ahe, hen, end, ndr, dra, ras, asi, sin, ing, ngh, ghd, hdh, dho, hon, oni]
  • Sorted substrings in lexicographical order: [ahe, asi, dho, dra, end, ghd, hdh, hen, hon, ing, mah, ndr, ngh, oni, ras, sin]
    • 7th smallest: hdh
    • 7th largest: ing

For the third example:

  • All possible substrings of length 2 are: [chennaisuper, hennaisuperk, ennaisuperki, nnaisuperkin, naisuperking, aisuperkings]
  • Sorted substrings in lexicographical order: [aisuperkings, chennaisuper, ennaisuperki, hennaisuperk, naisuperking, nnaisuperkin]
    • 7th smallest: INVALID
    • 7th largest: INVALID

Java Code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class NthLexicographicalSubstrings {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        String s = scanner.nextLine();
        int k = scanner.nextInt();
        int n = scanner.nextInt();

        ArrayList<String> substrings = new ArrayList<>();

        for (int i = 0; i <= s.length() - k; i++) {
            substrings.add(s.substring(i, i + k));
        }

        Collections.sort(substrings);

        String nthSmallest = (n <= substrings.size()) ? 
                                substrings.get(n - 1) : "INVALID";
        String nthLargest = (n <= substrings.size()) ? 
                substrings.get(substrings.size() - n) : "INVALID";

        System.out.println(nthSmallest);
        System.out.println(nthLargest);
    }
}

Insights:
  1. Scanner for Input: The program starts by creating a Scanner object to read input from the user, which includes a string and two integers (k and n).
  2. Substring Generation: The program generates all substrings of length k from the input string s by using a for-loop that iterates over valid starting indices (i.e., i from 0 to s.length() - k).
  3. Storage of Substrings: All substrings of length k are stored in an ArrayList called substrings. This allows for easy sorting and indexing later.
  4. Sorting Substrings: The list of substrings is sorted using Collections.sort(), which sorts the list in lexicographical (dictionary) order. Sorting is key for finding the smallest and largest substrings based on their lexicographical order.
  5. Indexing the Nth Smallest Substring: The program retrieves the nth smallest substring using the index n - 1 (since list indices are zero-based). If n is greater than the size of the list, it returns "INVALID".
  6. Indexing the Nth Largest Substring: The program retrieves the nth largest substring using the index substrings.size() - n (again, zero-based). If n is larger than the number of substrings, it returns "INVALID".
  7. Boundary Check for Substring Count: Both the nthSmallest and nthLargest are checked to ensure that n is within the valid range of substrings. If n exceeds the available substrings, the result will be "INVALID".
  8. Handling Edge Cases: The program is designed to handle cases where there are fewer than n substrings by outputting "INVALID" in both cases (smallest and largest substrings).
  9. Efficiency Considerations: The program generates all possible substrings of length k first, which results in a time complexity of O(n * k) for substring generation (where n is the length of the string). Sorting these substrings takes O(m log m) time, where m is the number of substrings.
  10. User-Friendly Output: The program outputs the nth smallest and nth largest substrings in separate lines, providing the results in a clear and user-friendly format.
Life is like searching for substrings—sometimes you have to sort through the chaos to find the smallest joys and the biggest opportunities. And just like in this program, even when things seem "INVALID," there's always another chance to try again!

Comments

Post a Comment