CODEWITHSUNDEEP
javastringcompareto
Divyanshu Sharma
Divyanshu Sharma

Reputation: 53

How to order substring lexographically

I want to order the substring of string 's' lexographically of length 'k'

I have tried to first sort the characters of the string lexographically using comapareTo function and then have tried to print the first and last substring

public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";
    char ch1,ch2,temp;
    int i,j,res; 

    // 'smallest' must be the lexicographically smallest substring of length 'k'
    // 'largest' must be the lexicographically largest substring of length 'k'
    for(i=0;i<s.length();i++)
    {
        ch1=s.charAt(i);
        for(j=i+1;j<=s.length();j++)
        {
            ch2=s.charAt(j);
            res=ch2.compareTo(ch1);
            if(res<0)
            {
                temp=ch2;
                ch2=ch1;
                ch1=temp;
            }
        }
    }
    smallest=s.substring(0,k);
    largest=s.substring(s.length()-k);
    return smallest + "\n" + largest;
}

expected output: Return the respective lexicographically smallest and largest substrings as a single newline-separated string.

input: welcometojava
3

expected output:ava
wel

Upvotes: 2

Views: 2910

Answers (2)

Yordan
Yordan

Reputation: 131

We initialize max and min as first substring of size k. We traverse remaining substrings, by removing first character of previous substring and adding last character of new string. We keep track of the lexicographically largest and smallest.

public class GFG { 

public static void getSmallestAndLargest(String s, int k) 
{ 
    // Initialize min and max as first substring of size k 
    String currStr = s.substring(0, k); 
    String lexMin = currStr; 
    String lexMax = currStr; 

    // Consider all remaining substrings. We consider 
    // every substring ending with index i. 
    for (int i = k; i < s.length(); i++) { 
        currStr = currStr.substring(1, k) + s.charAt(i); 
        if (lexMax.compareTo(currStr) < 0)      
             lexMax = currStr; 
        if (lexMin.compareTo(currStr) > 0) 
             lexMin = currStr;             
    } 

    // Print result. 
    System.out.println(lexMin); 
    System.out.println(lexMax); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
    String str = "GeeksForGeeks"; 
    int k = 3; 
    getSmallestAndLargest(str, k); 
}

}

Upvotes: 0

Mureinik
Mureinik

Reputation: 311198

You have the right idea, but you're attempting to compare single characters. Instead, in each iteration you should take a substring of length k, and compare it to the current "smallest" and "largest" strings:

public static String getSmallestAndLargest(String s, int k) {
    String curr = s.substring(0, k);
    String smallest = curr;
    String largest = curr;
    for (int i = 1; i < s.length() - k + 1; ++i) {
        curr = s.substring(i, i + k);
        if (smallest.compareTo(curr) > 0) {
            smallest = curr;
        }
        if (largest.compareTo(curr) < 0) {
            largest = curr;
        }
    }
    return smallest + "\n" + largest;
}

Upvotes: 1

Related Questions