In the coding round of this company, question was to find the longest substring having distinct characters.
Below is my solution for this problem, though I was not able to complete this in the given time frame, as I was having around 35 mins remaining for this, you can also check the related code given in Interview2
But may be it can help you to crack this or other such interview -
import java.util.HashMap;
/**
* Below question was asked to code in interview for BlueOptima.
* Question was to find the largest substring with distinct characters.
* Below is my solution, which I can think of for now with my a few below test cases.
* Please let me know the case for which it doesn't work.
* @author nitin
*
*/
public class BlueOptima {
public static void main(String args[]) {
System.out.println(LargestSubString("abcda")); // 4
System.out.println(LargestSubString("abadc")); // 4
System.out.println(LargestSubString("abadcbefg")); // 7
System.out.println(LargestSubString("abadcbeag")); // 6
System.out.println(LargestSubString("abadcbeagb")); // 6
System.out.println(LargestSubString("aaaaaaaaaa")); // 1
System.out.println(LargestSubString("abcddceaghi")); // 7
System.out.println(LargestSubString("abclmceaghi")); // 8
System.out.println(LargestSubString("abcddceag")); // 5
System.out.println(LargestSubString("abadcbeagbklmnop")); // 10
System.out.println(LargestSubString("abcdefghijklmf")); // 13
}
static int LargestSubString(String S){
int max = 0;
HashMap<Character, Integer> hm = new HashMap<>();
char[] chars = S.toCharArray();
int len = chars.length;
int start = 0;
for(int i = 0; i < len; i++) {
char ch = chars[i];
if(!hm.containsKey(ch)) {
hm.put(ch, i);
} else {
int pos = hm.get(ch);
if(pos != start) {
if(hm.size() > max)
max = hm.size();
int k = hm.get(chars[i]) + 1;
hm.clear();
start = k;
while(k < i) {
hm.put(chars[k], k);
k++;
}
} else {
start = pos + 1;
int k = pos;
while(k >= 0) {
if(hm.containsKey(chars[k]) && hm.get(chars[k]) == k)
hm.remove(chars[k]);
k--;
}
}
hm.put(ch, i);
}
}
if(hm.size() > max)
max = hm.size();
return max;
}
}
Below is my solution for this problem, though I was not able to complete this in the given time frame, as I was having around 35 mins remaining for this, you can also check the related code given in Interview2
But may be it can help you to crack this or other such interview -
import java.util.HashMap;
/**
* Below question was asked to code in interview for BlueOptima.
* Question was to find the largest substring with distinct characters.
* Below is my solution, which I can think of for now with my a few below test cases.
* Please let me know the case for which it doesn't work.
* @author nitin
*
*/
public class BlueOptima {
public static void main(String args[]) {
System.out.println(LargestSubString("abcda")); // 4
System.out.println(LargestSubString("abadc")); // 4
System.out.println(LargestSubString("abadcbefg")); // 7
System.out.println(LargestSubString("abadcbeag")); // 6
System.out.println(LargestSubString("abadcbeagb")); // 6
System.out.println(LargestSubString("aaaaaaaaaa")); // 1
System.out.println(LargestSubString("abcddceaghi")); // 7
System.out.println(LargestSubString("abclmceaghi")); // 8
System.out.println(LargestSubString("abcddceag")); // 5
System.out.println(LargestSubString("abadcbeagbklmnop")); // 10
System.out.println(LargestSubString("abcdefghijklmf")); // 13
}
static int LargestSubString(String S){
int max = 0;
HashMap<Character, Integer> hm = new HashMap<>();
char[] chars = S.toCharArray();
int len = chars.length;
int start = 0;
for(int i = 0; i < len; i++) {
char ch = chars[i];
if(!hm.containsKey(ch)) {
hm.put(ch, i);
} else {
int pos = hm.get(ch);
if(pos != start) {
if(hm.size() > max)
max = hm.size();
int k = hm.get(chars[i]) + 1;
hm.clear();
start = k;
while(k < i) {
hm.put(chars[k], k);
k++;
}
} else {
start = pos + 1;
int k = pos;
while(k >= 0) {
if(hm.containsKey(chars[k]) && hm.get(chars[k]) == k)
hm.remove(chars[k]);
k--;
}
}
hm.put(ch, i);
}
}
if(hm.size() > max)
max = hm.size();
return max;
}
}