akashgupta.edu
BAN USERSolution with O(n) complexity and without Hash Map.
This solution assumes that the string is comprised of only 'a-z' in lower case only. (But the solution can be extended for supporting other literals as well)
Hope this helps.
public String longestSubString(String str) {
String longestSubStr = "";
String longestSoFar = "";
int[] arr = new int[26];
for(int i=0;i<26; i++)
arr[i]=-1;
for(int i=0;i<str.length();i++) {
char charac = str.charAt(i);
int loc = charac -'a';
if(arr[loc]==-1) {
longestSoFar += charac;
arr[loc] = i;
}
else if(longestSoFar.length()<(i-arr[loc])){
longestSoFar += charac;
arr[loc] = i;
}
else {
if(longestSoFar.length()>longestSubStr.length()) {
longestSubStr = longestSoFar;
}
longestSoFar = str.substring(arr[loc]+1,i+1);
arr[loc] = i;
}
}
return longestSubStr;
}
no of Server = s
- akashgupta.edu April 12, 2014no of Task = t
Logic
1. Sort the server - O(s*logs)
2. Sort the Task - O(t*logt)
3. For i = t to 1
Bool task_scheduled = false
For j = 1 to s
if( T[ i ] < S[ j ] )
S[ j ] = S[ j ] - T[i]
task_scheduled = true
End For
if( !task_scheduled)
return false
End for
- O(s*t)
Worst case complexity - max of three
Will think of better solution and post