Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 9 vote

Assuming that a string is ASCII I would propose the following solution:

``````(i) 	Create histogram whit 128 bins initiated to zero and create counter
(ii) 	Initiate left/right pointers to 1st and 2nd char in a string
(iii)	Move right pointer if substring contains less or equal 'm' unique characters
Move left pointer if substring containc more than 'm' unique characters
(iv) 	Keep track of the longest substring``````

The solution should be O(N) time O(1) memory. A sample code is shown below:

``````public static String longestSubstring(String s, int m) {
int N = s.length();
int[] h = new int[128];
int cnt = 0;
int left = 0, right = 0;
int from = 0, to = 0;

while (left < N && right < N) {
if (cnt <= m) {
char c = s.charAt(right++);
if (h[c]++ == 0) 		cnt++;
}
else {
char c = s.charAt(left++);
if (h[c]-- == 0) 		cnt--;
}

if (to - from < right-left ) {
from = left;
to = right;
}
}

return s.substring(from, to);
}``````

Comment hidden because of low score. Click to expand.
2

The condition in else part should be
if(--h[c] == 0) cnt--;

Comment hidden because of low score. Click to expand.
0

Nice solution. Just note that if we use combination of hashmap and linked lists (like what we do for implementing LRU) for storing the position of character that we say, then the space will be O(2k) which is will be smaller (equal if k is 128) than your solution

Comment hidden because of low score. Click to expand.
2
of 2 vote

Java Implementation. Time: O(N); Space: O(N); HashMap and Moving Window idea.
This Question looks like a DP problem, but I can't find a DP solution better than this.
Does anybody have one?

``````import java.util.*;
public class LongestSubStringWithMUniqueChar {
public String getLSKQC(String source, int m) {
if (source == null || source.length() == 0 || m > source.length() || m <= 0) {
return "";
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
int left = 0;
int right = 0;
String res = "";
for (right = 0; right < source.length(); right++) {
char curt = source.charAt(right);
if (!map.containsKey(curt)) {
map.put(curt, 1);
} else {
map.put(curt, map.get(curt) + 1);
}

if (map.keySet().size() == m + 1) {
if (right - left > res.length()) {
res = source.substring(left, right);
}
while (map.keySet().size() > m) {
char c = source.charAt(left++);
if (map.get(c) == 1) {
map.remove(c);
} else {
map.put(c, map.get(c) - 1);
}
}
}
}
if (map.keySet().size() == m && right - left > res.length()) {
res = source.substring(left, right);
}
return res;
}
public static void main(String[] args) {
LongestSubStringWithKUniqueChar code = new LongestSubStringWithKUniqueChar();
System.out.println(code.getLSKQC("aabacbeaabacbb", Integer.parseInt(args[0])));
}
}``````

Comment hidden because of low score. Click to expand.
0

I don't think you need DP in this problem and your sliding window solution looks fine. If you assume that there is only a limited number of characters that can show up on your string (ASCII or the English alphabet, for example), you can claim your solution to be O(1) space.

Comment hidden because of low score. Click to expand.
1
of 1 vote

To get an O(n) time solution, use the following method (in pseudo-python):

``````find_unique_substring(big_string, unique_count):
ptr_1 = 0
ptr_2 = 1
uniques = {big_string[ptr_1]: 1}
curr_count = 1
max = ""
while ptr_2 < length of big_string:
if big_string[ptr_2] is already in uniques:
increment val by 1 for it
else:
set val to 1 for it
increment curr_count
if curr_count <= unique_count:
if length of big_string[ptr_1:ptr_2] > length of max:
max = big_string[ptr_1:ptr_2]
increment ptr_2
else:
decrement val for big_string[ptr_1] in uniques by 1
if val for big_string[ptr_1] == 0, decrement curr_count by 1
increment ptr_1 and ptr_2
return max``````

a little messy, but the general idea is since the substrings are contiguous you should only
need to run through the entire string once. As long as you keep track of what values youve seen
and whether or not any are still in the substring, and how many uniques are in the current substring,
you can find the max.

Comment hidden because of low score. Click to expand.
1
of 1 vote

how do you know when to discard a sequence when another better sequence might come upfront? for example: for 3 unique chars: aaabbccppxxzzaaaabkkkkzz

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string lss_unique(string str, int m){
int table[26];
int unique = 0;
int start, idx1, idx2;
int nMax, temp;

idx1 = idx2 = start = nMax = 0;
for (int i=0; i<26; i++)
table[i] = 0;

while(idx2 < str.size()){
while(idx2 < str.size() && unique <= m){
temp = str[idx2] - 'a';
table[temp]++;
if (table[temp] == 1)
unique++;
idx2++;
}
if (unique > m && nMax < ((idx2-1)-idx1)){
start = idx1;
nMax = (idx2-1)-idx1;
}
while(idx1 <= idx2 && unique >= m){
temp = str[idx1] - 'a';
table[temp]--;
if (table[temp] == 0)
unique--;
idx1++;
}
}
return str.substr(start,nMax);
}``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

The string may contain non alphabet charecters or upper case...

Comment hidden because of low score. Click to expand.
0

for m=3

Comment hidden because of low score. Click to expand.
0

GAURAV//
You are right. It does not handle the corner case properly. :(

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class substring_size
{
public static void main(String args[])
{
String s="aabbbaabcccbccc";
char c[]=s.toCharArray();
int m=3;     //unique characters
char ch[]= new char[m];
ch[0]=c[0];

int i=0;
int j=0;
while(i<ch.length-1)
{

if(ch[i]!=c[j])
{
if(present(ch,c[j],i))
{  j++;
continue;
}
ch[i+1]=c[j]; i++;
}
else
j++;
}
System.out.println(new String(ch));
String sub=s.substring(0,j+1);
while(j<c.length && c[j]==c[j+1])
{
sub+=c[j];
j++;
}
System.out.println(sub);

}
static boolean present(char c[],char ch,int k)
{
for(int i=0;i<k;i++)
{
if(ch==c[i])
return true;
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Working Java solution using moving window approach.

``````import java.util.HashMap;

public static int longestUniqueCharsSubstring(String s, int m) {
int maxLen = 0;  // keep track of max length substring so far

// current substring we're looking at is from [start, next)
int start = 0;
int next = 0;

// keep track of character counts of the characters in our substring
HashMap<Character, Integer> charCounts = new HashMap<Character, Integer>();
int nChars = 0;

while (next < s.length()) {
// increase the substring from the right as much as possible
while (next < s.length() && (nChars < m || charCounts.containsKey(s.charAt(next)))) {
char c = s.charAt(next);
if (charCounts.containsKey(c)) {
charCounts.put(c, 1 + charCounts.get(c));
} else {
charCounts.put(c, 1);
nChars++;
}
next++;
}

// at this point, we have the longest substring possible starting at "start"
maxLen = Math.max(maxLen, next - start);

// decrease the substring from the left until we're able to increase it
// from the right again
while (nChars != m - 1) {
char c = s.charAt(start);
charCounts.put(c, charCounts.get(c) - 1);
if (charCounts.get(c) == 0) {
nChars--;
charCounts.remove(c);
}
start++;
}
}

return maxLen;
}

public static void main(String[] args) {
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sliding window solution in java below:

``````public static String findLongestSubstringMUniqueChars(String s, int maxUniques) {
if (s == null || s.length() == 0 || s.length() < maxUniques) {
return null;
}

if (s.length() == maxUniques) {
return s;
}

int currentCharCount = 0;
int currentUniqueCharCount = 0;
int longestCharCount = 0;
int longestIndexInit = 0;
int longestIndexEnd = 0;

Set<Character> currentSet = new HashSet<>();
Set<Character> longestSet = new HashSet<>();

char[] chars = s.toCharArray();

int i = 0;
while (i < chars.length) {
Character c = chars[i];
if (currentUniqueCharCount < maxUniques) {
if (!currentSet.contains(c)) {
currentUniqueCharCount++;
}
currentCharCount++;

} else if (currentUniqueCharCount == maxUniques) {
if (!currentSet.contains(c)) {
if (longestCharCount < currentCharCount) {
longestCharCount = currentCharCount;
longestIndexInit = i - currentCharCount;
longestIndexEnd = i;
longestSet = currentSet;
}

currentSet = new HashSet<>();
i = i - currentCharCount;
currentCharCount = 0;
currentUniqueCharCount = 0;

} else {
currentCharCount++;
}
}
i++;
}

if (longestCharCount < currentCharCount) {
longestCharCount = currentCharCount;
longestIndexInit = i - currentCharCount;
longestIndexEnd = s.length()-1;
longestSet = currentSet;
}

return s.substring(longestIndexInit, longestIndexEnd);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int find(char *str,int k)
{
int i=0,j=0,max=0,start=0;
map<char,int> m;
char ch;
while(str[j]!='\0')
{
ch=str[j];
m[ch]++;
while(m.size()>k && i<j)
{
ch=str[i];
if(m[ch]>1)
m[ch]--;
else
m.erase(ch);
++i;
}
if(m.size()==k && max<(j-i))
{
max=j-i+1;
start=i;
}
++j;
}
i=start;
while(i<start+max)
{
printf("%c",str[i]);
i++;
}
return max;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int find(char *str,int k)
{
int i=0,j=0,max=0,start=0;
map<char,int> m;
char ch;
while(str[j]!='\0')
{
ch=str[j];
m[ch]++;
while(m.size()>k && i<j)
{
ch=str[i];
if(m[ch]>1)
m[ch]--;
else
m.erase(ch);
++i;
}
if(m.size()==k && max<(j-i))
{
max=j-i+1;
start=i;
}
++j;
}
i=start;
while(i<start+max)
{
printf("%c",str[i]);
i++;
}
return max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python sample

``````def find1 (a,unique):
res=""
res1=""
h = dict()
len1 = len(a)
for i in list(a):
if not h.has_key(i):
if unique !=0:
h[i]=1
unique = unique -1
res=res+i
else :
if len(res1) < len(res):
res1=res
res= ""
else:
res=res+i
print "hash=",h
if len(res1) > len(res):
res = res1
print res

a = "aabacbeaabacbbfaaaaaaaaaaabbbbbbbbbbbcccccccccaaaaar"
unique = 3
find1(a,unique)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

One way to simplify the problem is to group the same chars that are contiguous. Pre-process the string to generate an array of arrays.

Ex. aaabbccca -> [ [a,a,a], [b,b],[c,c,c], [a] ]

Now you can apply the sliding window concept except now you don't have to worry as much about tracking many indices.

Given m, slide along the array from i = 0 to preprocessedArray.length - m, reading a window of size m and adding the lengths of the m sub-arrays.

``````int max = 0, count = 0;
for (int i = 0; i < preprocessedArray.length - m; i++) {
for (int j = 0; j < m; j++) {
count += preprocessedArray[i + j];
}
if (currentCount > count) {
max = count;
}
}
return max;``````

Runtime and space is O(n)

The above implementation can be improved by not re-computing what has already been computed by always just adding the count of the character that has just been added to the sliding window and subtracting the count of the character that has just been removed from the sliding window.

``````int count = 0;
for (int j = 0; j < m; j++) {
count += preprocessedArray[j];
}
int max = count;
for (int i = m; i < preprocessedArray.length - m; i++) {
count += preprocessedArray[i];
count -= preprocessedArray[i - m];
if (count > max) {
max = count;
}
}
return max;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Same as Minimum Window Substring.

``````public String find(String str, int m) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int count = 0;
int start = 0, end = 0;
int max = 0, maxstart = 0;
while (end < str.length()) {
char c = str.charAt(end);
if (map.containsKey(c)) {
map.put(c, map.get(c)+1);
} else {
// the (m+1)th unique char come out
while (count == m) {
if ((end - start) > max) {
max = end - start;
maxstart = start;
}
char s = str.charAt(start);
map.put(s, map.get(s) - 1);
if (map.get(s) == 0) {
map.remove(s);
count--;
}
start++;
}
map.put(c, 1);
count++;
}
end++;
}
return str.substring(maxstart, maxstart+max);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

sliding window approach, in python:

``````from collections import defaultdict

def find_longest_substr(s, m):
if len(s) == 0:
return 0

unique = defaultdict(int)
start = 0
end = -1
increase = True
longest = 0

while True:
if increase:
end += 1
unique[s[end]] += 1
if len(unique) <= m:
if (end-start+1) > longest:
longest = end-start+1
if end == (len(s)-1):
break
else:
increase = False
else:
unique[s[start]] -= 1
if unique[s[start]] == 0:
del unique[s[start]]
start += 1
if len(unique) <= m:
increase = True
if (end-start+1) > longest:
longest = end-start+1
if end == (len(s)-1):
break

return longest

#main
#s="aabacbeabbed"
s="aabacbeaabacbb"
m=3
print find_longest_substr(s, m)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My first try on this one

``````String s = "aaaabbcddddsdsds";
char[] chars = s.toCharArray();
int idx1 = 0;
int idx2 = 0;
int numUnique = 5;
Set<Character> unique = new HashSet<Character>();
String longestString = "" + chars[0];
String longestString1 = "" + chars[0];
String strc0 = "";

while(idx2 < s.length()) {
if(idx1 != idx2) {
char c0 = chars[idx1];
strc0 += c0;
char c1 = chars[idx2];
if(unique.contains(c1)) {
if(unique.size() <= numUnique) {
longestString1 += c1;
idx2++;
}
} else {// not contains
if(unique.size() == numUnique) {
unique.clear();
idx1 = idx2;
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
longestString1 = strc0 + c1;
} else {
idx1 = idx2;
longestString1 += c1;
}
strc0 = "";
idx2++;
}
} else {
idx2++;
}
}

if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}

System.out.println(longestString);
System.out.println(longestString.length());``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````String s = "aaaabbcddddsdsds";
char[] chars = s.toCharArray();
int idx1 = 0;
int idx2 = 0;
int numUnique = 5;
Set<Character> unique = new HashSet<Character>();
String longestString = "" + chars[0];
String longestString1 = "" + chars[0];
String strc0 = "";

while(idx2 < s.length()) {
if(idx1 != idx2) {
char c0 = chars[idx1];
strc0 += c0;
char c1 = chars[idx2];
if(unique.contains(c1)) {
if(unique.size() <= numUnique) {
longestString1 += c1;
idx2++;
}
} else {// not contains
if(unique.size() == numUnique) {
unique.clear();
idx1 = idx2;
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
longestString1 = strc0 + c1;
} else {
idx1 = idx2;
longestString1 += c1;
}
strc0 = "";
idx2++;
}
} else {
idx2++;
}
}

if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}

System.out.println(longestString);
System.out.println(longestString.length());``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int FindLongestUniqueSubstring(char str[], int length) {

int* longest = new int[length]; // each element is the longest unique string ending at that index
int lastIndexSeenPlusOne[26];

for (int i = 0; i < 26; ++i) {
lastIndexSeenPlusOne[i] = 0; //flag for 'not seen', otherwise it is the index last seen plus one
}
for (int i = 0; i < length; ++i) {
longest[i] = 1; // every character is at least one character long
}
for (int i = 0; i < length; ++i) {
int index = str[i] - 97;// convert to index starting at 0, from ascii lower case assumed

if (i > 0) { // only for the 2nd+ itteration can we access longest[i - 1], however we still set lastIndexSeenPlusOne[index] after this block

if (lastIndexSeenPlusOne[index] > 0) {

longest[i] = (int)std::fmin(longest[i - 1] + 1, i - lastIndexSeenPlusOne[index]);
}
else {
longest[i] = longest[i - 1] + 1;
}
}

lastIndexSeenPlusOne[index] = i + 1;
}

int longestSeen = 0; // search for longest sequence found, that's our answer!
for (int i = 0; i < length; ++i) {
if (longest[i] > longestSeen) {
longestSeen = longest[i];
}
}
delete[] longest;

return longestSeen;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string longestSubstring(string &str, int n)
{
map<char,int> M;
string out ("");
for(int i=0;i<str.length();i++)
{
M[str[i]]++;
if(M.size() > n)
break;
out.push_back(str[i]);
}
return out;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string longestSubstring(string &str, int n)
{
map<char,int> M;
string out ("");
for(int i=0;i<str.length();i++)
{
M[str[i]]++;
if(M.size() > n)
break;
out.push_back(str[i]);
}
return out;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int f(const string& s, int m)
{
auto p0 = s.begin(), p1 = p0, best = p1;
int  c  = 1;
int  max_len = 1;
vector<bool> contains(0x100,false);

while (p1 != s.end()) {
while (c <= m) {
contains[*p1] = true;
if (++p1 == s.end()) break;
if (!contains[*p1]) c++;
}
if (p1 - p0 > max_len) {
max_len = p1 - p0;
best = p0;
}
contains[*p0] = false;
while(*p0 == *++p0) {}
c--;
}
return max_len;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int longestSubstring(String s, int m){
if(s == null || s.length() == 0 || m > s.length())
return 0;
Set<Character> unique = new HashSet<Character> ();
int leftBound = 0;
int max = 0;
String rst = "";
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(!unique.contains(c)){
if(unique.size() < m)
else{
char last = s.charAt(i - 1);
while(leftBound < i && s.charAt(leftBound) == last)
leftBound++;
char toRemove = s.charAt(leftBound);
while(leftBound < i && s.charAt(leftBound) == toRemove)
leftBound++;
unique.remove(toRemove);
}
}
if(i - leftBound + 1 > max){
max = i - leftBound + 1;
rst = s.substring(leftBound, i + 1);
}
}
System.out.println(rst);
return max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}

}
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

dynamic algorithm:

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}

}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}

}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package google.task;

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}

}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package google.task;

import java.util.HashSet;
import java.util.List;

public class UniqSubstr {

public static void main(String[] args) {
fun(string, subString);
}

final static int m = 2;
static List<Character> string = new LinkedList<>();
static List<Character> subString = new LinkedList<>();
static {
}

public static void fun(List<Character> string, List<Character> subString) {
for (int i = 0; i < string.size() - subString.size(); i++) {
List<Character> cand = string.subList(i, i + subString.size() + 1);
if ((new HashSet<Character>(cand)).size() <= m) {
subString = cand;
System.out.println("subString="+subString);
fun(string,subString);
break;
}

}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashSet;

public class muniquechar {

public static void main(String[] args) {
// TODO Auto-generated method stub
String s="aabacbeabbed";
int m=4;
HashSet<Character> x=new HashSet<Character>();
int maxlength=0;
for (int i=0;i<s.length()-1;i++){
int j=i;
x.clear();
for (;j<s.length() && x.size()<=m;j++)
{
}

if (x.size()>m && j-i>maxlength){
maxlength=j-i;
System.out.println("Length="+maxlength+" "+s.substring(i, j-1));
}

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashSet;

public class muniquechar {

public static void main(String[] args) {
// TODO Auto-generated method stub
String s="aabacbeabbed";
int m=4;
HashSet<Character> x=new HashSet<Character>();
int maxlength=0;
for (int i=0;i<s.length()-1;i++){
int j=i;
x.clear();
for (;j<s.length() && x.size()<=m;j++)
{
}

if (x.size()>m && j-i>maxlength){
maxlength=j-i;
System.out.println("Length="+maxlength+" "+s.substring(i, j-1));
}

}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static String longestSubstring(String s, int m) {
if(s.length() <= m) return s;

HashSet<Character> x=new HashSet<Character>();
int maxlength=0;
String maxString ="";
for (int i=0;i<s.length()-m;i++){
int j=i;
x.clear();
for (;j<s.length() && x.size()<=m;j++)
{
if(x.size() < m) {
}
else {
if(x.contains(s.charAt(j)))
else
break;
}
}

String curr = s.substring(i, Math.min(s.length(), j));
if(curr.length() > maxlength) {
maxlength = curr.length();
maxString = curr;
}
}

//System.out.println("The sring is " + maxlength + " " + maxString);
return maxString;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String longestSubstring(String s, int m) {
if(s.length() <= m) return s;

HashSet<Character> x=new HashSet<Character>();
int maxlength=0;
String maxString ="";
for (int i=0;i<s.length()-m;i++){
int j=i;
x.clear();
for (;j<s.length() && x.size()<=m;j++)
{
if(x.size() < m) {
}
else {
if(x.contains(s.charAt(j)))
else
break;
}
}

String curr = s.substring(i, Math.min(s.length(), j));
if(curr.length() > maxlength) {
maxlength = curr.length();
maxString = curr;
}
}

//System.out.println("The sring is   " + maxlength + " " + maxString);
return maxString;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static String longestSubstring(String s, int m) {
if(s.length() <= m) return s;

HashSet<Character> x=new HashSet<Character>();
int maxlength=0;
String maxString ="";
for (int i=0;i<s.length()-m;i++){
int j=i;
x.clear();
for (;j<s.length() && x.size()<=m;j++)
{
if(x.size() < m) {
}
else {
if(x.contains(s.charAt(j)))
else
break;
}
}

String curr = s.substring(i, Math.min(s.length(), j));
if(curr.length() > maxlength) {
maxlength = curr.length();
maxString = curr;
}
}

//System.out.println("The sring is   " + maxlength + " " + maxString);
return maxString;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````template <typename K, typename V>
using map = boost::unordered_map<K, V>;

int longest_unique_substr(const std::string& s, const int m)
{
if (s.empty()) return 0;
if (0 == m) return 0;
auto max = 1;
auto start = 0;
auto end = 0;
map<char, int> counts;
counts[s[0]] = 1;
for (auto i = 1; i < s.length(); ++i)
{
end = i;
if (counts.find(s[i]) != counts.end())
{
counts[s[i]] += 1;
}
else
{
counts[s[i]] = 1;
if (counts.size() > m)
{
while (start < end)
{
counts[s[start]] -= 1;
if (0 == counts[s[start]])
{
counts.erase(s[start]);
++start;
break;
}
++start;
}
}
}
if (end - start + 1 > max)
{
max = end - start + 1;
}
}
return max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript - sliding window

``````var input = "aabacbeabbeed";

function getLongestMUniqCharSubstr(input, m)
{
if(!m) return "";

var longest = "";
var current = "";
var needed = m;

var left = 0, right = 0;

while(right < input.length){

if(needed > 0){
current+=input[right++];
if(current.indexOf(input[right]) == -1)
needed--;
}
else if(needed <= 0){
if(current.length > longest.length) longest = current;
var charLeft = input[left];
while(current.indexOf(charLeft) >= 0) {
left++;
current = current.slice(1);
}
needed++;
}

}

return longest || current;

}

console.log(getLongestMUniqCharSubstr(input, 3));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript - sliding window

``````var input = "aabacbeabbeed";

function getLongestMUniqCharSubstr(input, m)
{
if(!m) return "";

var longest = "";
var current = "";
var needed = m;

var left = 0, right = 0;

while(right < input.length){

if(needed > 0){
current+=input[right++];
if(current.indexOf(input[right]) == -1)
needed--;
}
else if(needed <= 0){
if(current.length > longest.length) longest = current;
var charLeft = input[left];
while(current.indexOf(charLeft) >= 0) {
left++;
current = current.slice(1);
}
needed++;
}

}

return longest || current;

}

console.log(getLongestMUniqCharSubstr(input, 3));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````function getLongestMUniqCharSubstr(input, m)
{
if(!m) return "";

var longest = "";
var candidate = "";
var charMaps = {};

var left = 0, right = 0;

while(right < input.length){

charMaps[input[right]] || (charMaps[input[right]] = 0);
charMaps[input[right]]++;
right++;

if(Object.keys(charMaps).length == m && !charMaps[input[right]]) {
candidate = input.substring(left, right);
if (candidate.length > longest.length) longest = candidate;

while (Object.keys(charMaps).length >= m) {
var charLeft = input[left];
charMaps[charLeft]--;
if (charMaps[input[left]] == 0) delete charMaps[charLeft];
left++;
}
}

}

return longest;

}

console.log(getLongestMUniqCharSubstr("aabacbeabbeeed", 2));
console.log(getLongestMUniqCharSubstr("aabacbeabbeeed", 3));
console.log(getLongestMUniqCharSubstr("abaaaceeeeee", 2));
console.log(getLongestMUniqCharSubstr("abaaaceeeeee", 3));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static String findSubstring(String str, int n) {
String result = "";

for (int i = 0; i < str.length(); i++) {
if (str.length() - i <= result.length())
continue;
for (int j = str.length(); j > i; j--) {
String subChain = str.substring(i, j);
if (hasUniqueCharacters(subChain, n) && result.length() < subChain.length())
result = subChain;

}
}
return result;
}

static boolean hasUniqueCharacters(String str, int n) {
Set<Character> uniques = new HashSet<Character>();

for (int i = 0; i < str.length(); i++) {
if (uniques.size() > n) {
return false;
}
}
return uniques.size() == n ? true : false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

input
Str="aaabbabbcaaaaaaaaaaaaaaaaaccccccccc", m=2

Loop it for the first time and create a list of char and it counts like below
a-3
b-2
a-1
b-2
c-1
a-17
c-9

In second loop parse through list.
since m=2, take first 2 items from list
a-3 and b-2
then try to add third item and see if by adding third item, can we still have 2 unique char. If yes, then add it.
a-3, b-2, a-1
then try to add forth item and see if by adding forth item, can we still have 2 unique char. If yes, then add it.
a-3, b-2, a-1, b-2
then try adding fifth item which is 'c'. So by adding this, number of unique char will cross the threshold.
So take the count and store it in variable say maxLength which is equal to 3+2+1+2 = 8

Now start fresh new parsing element from fifth item
c-1
then add 6th item and see if its possible or not
c-1, a-17
then add 7th item which is again possible in our case
c-1, a-17, c-9
Now we reached the end. So find the sum and update maxLength if required

``````if ((1+17+9) > maxLength){
maxLentgh = (1+17+9)
}``````

Time complexity O(2n) = O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_string(strng,k):
list_s=set(strng)
subval=''
tempsub=''
tempsub2=''
val_list=[]
for val in list_s:
for idxt,cs in enumerate(strng):
if val == cs:
index_val = idxt
val_list.append(val)

for idx,d in enumerate(strng[index_val+1:]):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub = strng[index_val:idx+index_val+2]
print (str(1)+tempsub)

val_list=[]
val_list.append(val)

for idx,d in enumerate(''.join(reversed(strng[:index_val]))):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub2 = ''.join(reversed(strng[index_val-idx:index_val+1]))
print(str(2)+tempsub2)

val_list=[]

if len(tempsub2) > len(tempsub):
substr = tempsub2
else:
substr = tempsub
if len(substr)> len(subval):
subval = substr

return subval + str(len(subval))

s = "aabacbeabbed"
k=3
print(find_string(s,k))

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_string(strng,k):
list_s=set(strng)
subval=''
tempsub=''
tempsub2=''
val_list=[]
for val in list_s:
for idxt,cs in enumerate(strng):
if val == cs:
index_val = idxt
val_list.append(val)

for idx,d in enumerate(strng[index_val+1:]):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub = strng[index_val:idx+index_val+2]
print (str(1)+tempsub)

val_list=[]
val_list.append(val)

for idx,d in enumerate(''.join(reversed(strng[:index_val]))):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub2 = ''.join(reversed(strng[index_val-idx:index_val+1]))
print(str(2)+tempsub2)

val_list=[]

if len(tempsub2) > len(tempsub):
substr = tempsub2
else:
substr = tempsub
if len(substr)> len(subval):
subval = substr

return subval + str(len(subval))

s = "aabacbeabbed"
k=3
print(find_string(s,k))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_string(strng,k):
list_s=set(strng)
subval=''
tempsub=''
tempsub2=''
val_list=[]
for val in list_s:
for idxt,cs in enumerate(strng):
if val == cs:
index_val = idxt
val_list.append(val)

for idx,d in enumerate(strng[index_val+1:]):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub = strng[index_val:idx+index_val+2]
print (str(1)+tempsub)

val_list=[]
val_list.append(val)

for idx,d in enumerate(''.join(reversed(strng[:index_val]))):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub2 = ''.join(reversed(strng[index_val-idx:index_val+1]))
print(str(2)+tempsub2)

val_list=[]

if len(tempsub2) > len(tempsub):
substr = tempsub2
else:
substr = tempsub
if len(substr)> len(subval):
subval = substr

return subval + str(len(subval))

s = "aabacbeabbed"
k=3
print(find_string(s,k))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def find_string(strng,k):
list_s=set(strng)
subval=''
tempsub=''
tempsub2=''
val_list=[]
for val in list_s:
for idxt,cs in enumerate(strng):
if val == cs:
index_val = idxt
val_list.append(val)

for idx,d in enumerate(strng[index_val+1:]):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub = strng[index_val:idx+index_val+2]
print (str(1)+tempsub)

val_list=[]
val_list.append(val)

for idx,d in enumerate(''.join(reversed(strng[:index_val]))):
if d not in val_list:
val_list.append(d)
if len(val_list) == k:
tempsub2 = ''.join(reversed(strng[index_val-idx:index_val+1]))
print(str(2)+tempsub2)

val_list=[]

if len(tempsub2) > len(tempsub):
substr = tempsub2
else:
substr = tempsub
if len(substr)> len(subval):
subval = substr

return subval + str(len(subval))

s = "aabacbeabbed"
k=3
print(find_string(s,k))``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.