print the lexicographically smallest and largest substring of a given size k from a string s

Question

Its a program to print the Lexicographically smallest and largest substring of size k.

There´s a part in this solution I don´t really understand. Maybe someone can explain it to me.

 public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";
    String currStr = s.substring(0, k); 

---

Here is the part I dont get. why is int i initialised with k and how does

for(int i = k; i<s.length(); i++){
    currStr = currStr.substring(1, k) + s.charAt(i);

exactly work?

---

Full loop:

    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;             
    }       
    return smallest + "\n" + largest;
}

Answer 1

The idea of the algorithm that currStr goes through all substrings of length k. It starts with substring from index 0 to index k-1:

String currStr = s.substring(0, k); // end index is excluded!

Then to get the next substring, the one from index 1 to k:

• First it drops the first character from currStr, so you get a substring from index 1 to index k-1.

• Then it adds the character from index k from the input string. The end result is the substring from index 1 to index k.

This process is then repeated to get the substring from index 2 to k+1 and all the following substrings.

currStr = currStr.substring(1, k) // drop the first character from currStr
             + s.charAt(i);       // add next character from input string