Find character at given index in a sorted sub strings [closed]

Question

For a given string say dbac the possible substrings are [d,db,dba,dbac,b,ba,bac,a,ac,c]. Sort them and concatenate to a string: aacbbabaccddbdbadbac. Find the character at index m=2, so the answer is c.

Here is my code:

public char solve(String s, int m) {
    int n = s.length();
    List<String> list = new ArrayList<>();
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<=n; j++) {
            list.add(s.substring(i,j));
        }
    }
    Collections.sort(list);
    for(String s1 : list) {
        int q = s1.length();
        if(m >=q) m -=q;
        else {
            return s1.charAt(m);
        }
    }
    return ' ';
}

The time complexity of this code is \$O(n^3)\$ because nested for loops and substring methods.

Is there a way to solve this with lower time complexity?

Answer 1

Edit: ~~This avoids O(n^3) and should be run in O(n^2).~~

This potentially avoids O(n^3) time.

It avoids using substrings and creating new strings each time.

The space complexity is therefore only O(1) or O(n).

Please perform a benchmark test of both approaches...

import java.util.Comparator;
import java.util.TreeSet;

public class Substrings {
    record Elem(int from, int to) {
    }

    public char solve(final String s, final int m) {
        TreeSet<Elem> set = new TreeSet<>(Comparator.comparing(e -> s.substring(e.from(), e.to())));
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                set.add(new Elem(i, j));
            }
        }

        int m1 = m;
        for (Elem e : set) {
            int len = e.to() - e.from();
            if (m1 < len) {
                return s.substring(e.from(), e.to())
                        .charAt(m1);
            }
            m1 -= len;
        }

        return ' ';
    }

    public void testSolve() {
        String s = "dbac";
        StringBuilder r = new StringBuilder();
        for (int i = 0; i <= 25; i++) {
            System.out.println("i = " + i);
            System.out.println("r = " + r.append(solve(s, i)));
            System.out.println("---");
        }
    }

    public static void main(String[] args) {
        new Substrings().testSolve();
    }
}