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

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++) {
}
}
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?

• I wasn't sure you were going to repost so I wrote up my answer here while it was fresh in my mind: stackoverflow.com/questions/77161408/…
– Dave
Sep 23 at 19:56
• If the characters aren't unique you can probably use a suffix array. Oct 13 at 4:44
• The code presented is identical to the one in this older SO post by another user - disclosed as third party there. Oct 16 at 6:53

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++) {
}
}

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

• avoids O(n^3) How so? How many strings get add()ed, and how many characters compared on any one add()/all add()s combined? Oct 16 at 6:58
• Let n be the number of substrings. n^2/2 strings get added. Each string gets log_2(n) times compared. O(n^2/2 * log_2(n)) is not O(n^3). The space complexity is almost O(1) or O(n). Oct 16 at 7:36
• O(n^2/2 * log_2(n)) is not O(n^3) True, but Strings do not compare in O(1). Oct 16 at 7:45
• When m is the number of chars in both strings, then two strings can be compared in approximately m/2 time. So, I don't see O(n^3) yet. BTW. "Let n be the number of substrings" was wrong. Oct 16 at 7:55