Input: str="abcdeefuiuiwiwwaaaa" n=3 output: "iwiwwaaaa" (longest substr with 3 diff chars)
I have a solution as below. My questions:
- How is the time complexity? I know it must be better than O(n^2), but not sure whether can conclude it's O(n).
The solution below can not cover the whole ASCII, can we improve this without additional space?
public static String getSubstrOfMChars(String str, int m) { if (str==null || str.length()==0) return ""; int len = str.length(); String max = ""; for(int i=0; i<len;) { StringBuilder sb = new StringBuilder(); int counter = 1; int checker = 0; char firstChar = str.charAt(i); int firstCharPos = i; // first char position in the string sb.append(firstChar); checker |= 1 << (firstChar - 'a'); for(int j=i+1; j<len; j++) { char currChar = str.charAt(j); if (currChar == firstChar) firstCharPos++; int tester = checker & (1<<(currChar - 'a')); if ( tester > 0 ) // already have such character { sb.append(currChar); continue; } // new character if (++counter > m) { i = firstCharPos + 1; if (sb.length() > max.length()) { max = sb.toString(); } break; } sb.append(currChar); checker |= 1 << (currChar - 'a'); } if (counter <= m) { if ((counter==m) && sb.length() > max.length()) { max = sb.toString(); } break; } } return max; }