Как заказать подстроку лексографически

Question

Я хочу заказать подстроку строки 's' лексографически длиной 'k'

Я попытался сначала отсортировать символы строки лексографически, используя функцию comapareTo, а затем попытался напечататьпервая и последняя подстрока

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;
}

ожидаемый результат: возврат соответствующих лексикографически наименьших и наибольших подстрок в виде одной строки, разделенной новой строкой.

input: welcometojava
3

expected output:ava
wel

Answer 1

У вас правильная идея, но вы пытаетесь сравнить отдельные символы.Вместо этого в каждой итерации вы должны взять подстроку длиной k и сравнить ее с текущими «самыми маленькими» и «самыми большими» строками:

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;
}

Answer 2

Мы инициализируем max и min как первую подстроку размера k. Мы пересекаем оставшиеся подстроки, удаляя первый символ предыдущей подстроки и добавляя последний символ новой строки. Мы отслеживаем лексикографически самые большие и самые маленькие.

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); 
} 

}