Google Interview Question
Country: United States
Interview Type: In-Person
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])));
}
}
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:
add big_string[ptr_2] to uniques:
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.
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);
}
Your code gives wrong answer for str="aabacbeaabacbb"
Correct answer: "aabacbb" length=7
Your answer: "aabacb" length=6
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;
}
}
Working Java solution using moving window approach.
import java.util.HashMap;
public class LongestUniqueCharsSubstring {
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) {
System.out.println(longestUniqueCharsSubstring(args[0], Integer.parseInt(args[1])));
}
}
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)) {
currentSet.add(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);
}
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;
}
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;
}
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)
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;
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);
}
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)
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];
unique.add(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();
unique.add(c0);
unique.add(c1);
idx1 = idx2;
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
longestString1 = strc0 + c1;
} else {
idx1 = idx2;
unique.add(c1);
longestString1 += c1;
}
strc0 = "";
idx2++;
}
} else {
idx2++;
}
}
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
System.out.println(longestString);
System.out.println(longestString.length());
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];
unique.add(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();
unique.add(c0);
unique.add(c1);
idx1 = idx2;
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
longestString1 = strc0 + c1;
} else {
idx1 = idx2;
unique.add(c1);
longestString1 += c1;
}
strc0 = "";
idx2++;
}
} else {
idx2++;
}
}
if(longestString1.length() > longestString.length()) {
longestString = longestString1;
}
System.out.println(longestString);
System.out.println(longestString.length());
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;
}
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;
}
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)
unique.add(c);
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);
unique.add(c);
}
}
if(i - leftBound + 1 > max){
max = i - leftBound + 1;
rst = s.substring(leftBound, i + 1);
}
}
System.out.println(rst);
return max;
}
{package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
}
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
dynamic algorithm:
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
package google.task;
import java.util.HashSet;
import java.util.LinkedList;
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 {
string.add('a');
string.add('b');
string.add('c');
string.add('c');
string.add('c');
string.add('c');
string.add('z');
string.add('c');
}
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;
}
}
}
}
Whats so hard about this ? Just use a hashset with a sliding window
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++)
{
x.add(s.charAt(j));
}
if (x.size()>m && j-i>maxlength){
maxlength=j-i;
System.out.println("Length="+maxlength+" "+s.substring(i, j-1));
}
}
}
}
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++)
{
x.add(s.charAt(j));
}
if (x.size()>m && j-i>maxlength){
maxlength=j-i;
System.out.println("Length="+maxlength+" "+s.substring(i, j-1));
}
}
}
}
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) {
x.add(s.charAt(j));
}
else {
if(x.contains(s.charAt(j)))
x.add(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;
}
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) {
x.add(s.charAt(j));
}
else {
if(x.contains(s.charAt(j)))
x.add(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;
}
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) {
x.add(s.charAt(j));
}
else {
if(x.contains(s.charAt(j)))
x.add(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;
}
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;
}
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));
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));
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));
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++) {
uniques.add(str.charAt(i));
if (uniques.size() > n) {
return false;
}
}
return uniques.size() == n ? true : false;
}
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)
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))
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))
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))
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))
Assuming that a string is ASCII I would propose the following solution:
The solution should be O(N) time O(1) memory. A sample code is shown below:
- autoboli March 12, 2015public 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); }