Google Interview Question Software Developers
Country: United States
Here's my submission in C++14. I chose to design my code for readability since no requirements were placed on the size of k or the string.
#include <queue>
#include <string>
#include <iostream>
#include <unordered_set>
using namespace std;
int NumUniqueCharacters( const deque<char>& cur_substr )
{
static unordered_set<char> unique_chrs;
unique_chrs.clear();
for( auto itr = cur_substr.begin(); itr != cur_substr.end(); ++itr )
unique_chrs.insert( *itr );
return unique_chrs.size();
}
string KthLongestDistinctSubString( const string& str, const int& k )
{
deque<char> substr_buf;
string largest_substr;
for( const char& chr : str )
{
substr_buf.push_back( chr );
if( NumUniqueCharacters( substr_buf ) > k )
substr_buf.pop_front();
if( largest_substr.size() < substr_buf.size() )
largest_substr = string( substr_buf.begin(), substr_buf.end() );
}
return largest_substr;
}
int main()
{
string str_to_search;
int k;
cin >> str_to_search >> k;
cout << KthLongestDistinctSubString( str_to_search, k ) << endl;
return 0;
}
Following is what I tried, after coming up with examples.
private static String KthLongestDistinctSubString(String string, int numChars) {
int j = 0, distinct = 0;
String result = "";
char[] ch = string.toCharArray();
for (int i = 0; i < string.length(); i++) {
j = i;
StringBuffer sb = new StringBuffer();
int[] charAscii = new int[26];// 0,0,0,
while (j < string.length()) // aaaabbbb
{
char chac = ch[j];
if (charAscii[chac-'a'] > 0) {
sb.append(chac);
}
if (charAscii[chac-'a'] == 0) {
if (distinct > numChars)
break;
distinct++;
sb.append(chac);
charAscii[chac-'a'] = 1;
}
j++;
}
if (result.length() < sb.toString().length()) {
result = sb.toString();
}
}
return result;
}
package main
import (
"fmt"
"strings"
)
func KthLongestDistinctSubString(s string, k int) []string {
letters := strings.Split(s, "")
start := 0
i := 1
j := k
for j > 0 {
if len(letters) == i {
j--
i++
break
}
if letters[i-1] != letters[i] {
j--
}
i++
}
if j != 0 {
return []string{}
}
max := i - start - 1
result := []string{s[0 : i-1]}
for i < len(letters) {
for letters[start] == letters[start+1] {
start++
}
start++
for i < len(letters) && letters[i-1] == letters[i] {
i++
}
i++
if max == i-start-1 {
result = append(result, s[start:i-1])
}
if max < i-start-1 {
max = i - start - 1
result = []string{s[start : i-1]}
}
}
return result
}
func main() {
fmt.Println(KthLongestDistinctSubString("aaaabbbb", 2))
fmt.Println(KthLongestDistinctSubString("asdfrttt", 3))
fmt.Println(KthLongestDistinctSubString("aassdfrttt", 3))
}
#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
using namespace std;
int main() {
string in;
int k;
cin >> in >> k;
int curr_len = 0;
int max_l = 0;
unordered_set<char> distinct_chars;
queue<char> dist_chars_order;
for (int i = 0; i < in.size(); ++i) {
dist_chars_order.push(in[i]);
distinct_chars.insert(in[i]);
++curr_len;
if (distinct_chars.size() == k) {
max_l = std::max(max_l, curr_len);
}
if (distinct_chars.size() > k) {
char top = dist_chars_order.front();
while (dist_chars_order.front() == top) {
dist_chars_order.pop();
--curr_len;
}
distinct_chars.erase(distinct_chars.find(top));
}
}
cout << max_l << endl;
return 0;
}
#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
using namespace std;
int main() {
string in;
int k;
cin >> in >> k;
int curr_len = 0;
int max_l = 0;
unordered_set<char> distinct_chars;
queue<char> dist_chars_order;
for (int i = 0; i < in.size(); ++i) {
dist_chars_order.push(in[i]);
distinct_chars.insert(in[i]);
++curr_len;
if (distinct_chars.size() == k) {
max_l = std::max(max_l, curr_len);
}
if (distinct_chars.size() > k) {
char top = dist_chars_order.front();
while (dist_chars_order.front() == top) {
dist_chars_order.pop();
--curr_len;
}
distinct_chars.erase(distinct_chars.find(top));
}
}
cout << max_l << endl;
return 0;
}
import java.util.*;
import java.lang.*;
import java.io.*;
public class Solution {
Map<Character,Integer> map=new HashMap<Character,Integer>();
Boolean function(String string,int kval){
char array[]=string.toCharArray();
for(int i=0;i<array.length;i++){
if(map.containsKey(array[i])==false){map.put(array[i],1);}
}
if(map.size()==kval){
map.clear();
return true;
}
else{
map.clear();
return false;}
}
Set<String> Hash = new HashSet<String>();
void getSubstring(String strng,int Kval){
if(function(strng, Kval)==true){Hash.add(strng);}
else{
String st1=strng.substring(0,strng.length()-1);
String st2=strng.substring(1,strng.length());
getSubstring(st1, Kval);
getSubstring(st2, Kval);
}
}
void showSet(){
System.out.println(Hash);
}
public static void main(String[] args) {
Solution solution=new Solution();
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
String st=sc.next();
solution.getSubstring(st, k);
solution.showSet();
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
public class Solution {
Map<Character,Integer> map=new HashMap<Character,Integer>();
Boolean function(String string,int kval){
char array[]=string.toCharArray();
for(int i=0;i<array.length;i++){
if(map.containsKey(array[i])==false){map.put(array[i],1);}
}
if(map.size()==kval){
map.clear();
return true;
}
else{
map.clear();
return false;}
}
Set<String> Hash = new HashSet<String>();
void getSubstring(String strng,int Kval){
if(function(strng, Kval)==true){Hash.add(strng);}
else{
String st1=strng.substring(0,strng.length()-1);
String st2=strng.substring(1,strng.length());
getSubstring(st1, Kval);
getSubstring(st2, Kval);
}
}
void showSet(){
System.out.println(Hash);
}
public static void main(String[] args) {
Solution solution=new Solution();
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
String st=sc.next();
solution.getSubstring(st, k);
solution.showSet();
}
}
I made it heavily documented - thus...
// fully declarative --> un-optimal
def k_distinct_d( string , k ){
// create a range
r = [ 0 : size(string) ]
// create combination pair
pairs = list ( comb( r , 2 ) )
// sort them by their size : end_index - start_index
sortd ( pairs ) :: { ( $.left.1 - $.left.0 ) < ( $.right.1 - $.right.0 ) }
// find a pair such that the distinct chars are exactly equal to k
v = find ( pairs ) :: { s = string[$.left:$.right] ; size(set(s.value)) == k }
// yep, we are good
v.nil?'nothing found':string[ v.value.0 : v.value.1 ]
}
s = k_distinct_d("asdfrttt", 3)
println(s)
// semi imperative : reasonably optimal
def k_distinct_i( string , k ){
// we need to generate pairs with larger size first..so
len = size(string)
r = [0:len]
MAX = [ '' ] // global is frowned upon, use side effect
res = join ( r, r.reverse ) :: {
continue( $.0 >= $.1 )
s = string[ $.0 : $.1 ]
continue( size( set(s.value) ) != k || size(s) <= size(MAX.0) )
MAX.0 = s // set max
false // do not collect
}
empty(MAX.0) ? 'nothing found' : MAX.0
}
s = k_distinct_i("asdfrttt", 3)
println(s)
internal static string GetMaxSubstring(string input, int k)
{
if ((String.IsNullOrWhiteSpace(input)) ||
(input.Length < k) ||
(k <= 0))
{
return string.Empty;
}
int left = 0, right = 0, start = 0, maxLength = 0;
HashSet<char> hash = new HashSet<char>();
while (right < input.Length)
{
if (!hash.Contains(input[right]))
{
hash.Add(input[right]);
}
var length = right - left + 1;
// If we have k distinct elements in the hash,
// get the substring between left and right
// and see if it is longer that previous substring
if (hash.Count == k)
{
if (length > maxLength)
{
start = left;
maxLength = length;
}
}
// If we have one more than k distinct elements in the
// hash, then we need to remove the first element in the
// hash and update the left accordingly
if (hash.Count == k + 1)
{
// Move left as long as we keep encountering
// the input[left] character
var leftChar = input[left];
while (input[left] == leftChar)
{
left++;
}
// Remove the character from the hash
hash.Remove(leftChar);
}
// Move to the next character
right++;
}
// Create the substring
return input.Substring(start, maxLength);
}
public String getLongestDistinctString(String s, int k) {
if (s == null || k <= 0) {
return null;
}
final HashMap uniqueChars = new HashMap();
String lastString;
String longestString = "";
char currentChar;
for (int index = 0; index < s.length(); index ++) {
currentChar = s.charAt(index);
if (!uniqueChars.contains(currentChar) && uniqueChars.size() >= k) {
if (longestString.length() < lastString.lenght()) {
longestString = lastString;
}
char charToRemove;
int indexOfCharToRemove = lastString.length();
for (Entry entry : uniqueChars.entrySet) {
if (entry.getValue() < indexOfCharToRemove) {
indexOfCharToRemove = entry.getValue();
charToRemove = entry.getKey()
}
}
uniqueChars.remove(charToRemove);
final int newStartIndex = indexOfCharToRemove + 1;
lastString = lastString.subString(newStartIndex);
// Reset the indexes of the uniqueChars
for (Entry entry : uniqueChars.entrySet) {
entry.setValue(entry.getValue() - newStartIndex);
}
}
uniqueChars.put(char, lastString.length())
lastString += currentChar
}
return longestString;
}
#Solution in Python
def longestsubstring(mystring,k):
allsubstrings=list()
currentsubstring=""
distictchars=list()
for i in range(len(mystring)):
if len(distictchars) == k and mystring[i] not in distictchars:
allsubstrings.append(currentsubstring)
currentsubstring=""
distictchars=[]
if mystring[i] not in distictchars:
distictchars.append(mystring[i])
currentsubstring+=mystring[i]
if len(distictchars) == k:
allsubstrings.append(currentsubstring)
print allsubstrings
return
longestsubstring("asdfrttt",3)
!/usr/bin/env python2.7
class CharSet:
def __init__(self):
self.chars = {}
def has(self, c):
return c in self.chars
def size(self):
return len(self.chars)
def evict(self):
to_evict = min(self.chars.items(), key=lambda (c, last_seen): last_seen)
self.chars.pop(to_evict[0])
return to_evict
def add(self, c, last_seen):
self.chars[c] = last_seen
def solve(s, k):
longest = ''
chars = CharSet()
start = 0
for i, c in enumerate(s):
if not chars.has(c) and chars.size() >= k:
ss = s[start : i]
longest = max(longest, ss, key=len)
ec, ec_last_seen = chars.evict()
start = ec_last_seen + 1
chars.add(c, i)
ss = s[start :]
longest = max(longest, ss, key=len)
return longest
if __name__ == '__main__':
print solve("asdftttg", 3) # dfttt
print solve("asdfttdg", 3) # dfttd
print solve("asdfttdgg", 5) # sdfttdgg
#!/usr/bin/env python2.7
class CharSet:
def __init__(self):
self.chars = {}
def has(self, c):
return c in self.chars
def size(self):
return len(self.chars)
def evict(self):
to_evict = min(self.chars.items(), key=lambda (c, last_seen): last_seen)
self.chars.pop(to_evict[0])
return to_evict
def add(self, c, last_seen):
self.chars[c] = last_seen
def solve(s, k):
longest = ''
chars = CharSet()
start = 0
for i, c in enumerate(s):
if not chars.has(c) and chars.size() >= k:
ss = s[start : i]
longest = max(longest, ss, key=len)
ec, ec_last_seen = chars.evict()
start = ec_last_seen + 1
chars.add(c, i)
ss = s[start :]
longest = max(longest, ss, key=len)
return longest
if __name__ == '__main__':
print solve("asdftttg", 3) # dfttt
print solve("asdfttdg", 3) # dfttd
print solve("asdfttdgg", 5) # sdfttdgg
public static void main(String[] argc){
String str="asdfrttt";
int k =3;
HashSet<String> validString = new HashSet<String>();
System.out.println(getlongestSubstring(str,0, str.length(), k, validString));
int max = Integer.MIN_VALUE;
String LongestStr = new String();
for(String a: validString){
if(max<a.length())
{ max = a.length();
LongestStr = a;
}
}
System.out.println(LongestStr);
}
private static int uniqueCharCount(String str, int start, int end){
HashSet<Character> set= new HashSet<Character>();
for(int i=start; i<end; i++){
set.add(str.charAt(i));
}
return set.size();
}
private static int getlongestSubstring(String str, int start, int end, int k, HashSet<String> validString){
if(start <0 || end >str.length())
return 0;
if(k== uniqueCharCount(str,start,end)){
validString.add(str.substring(start,end));
return end-start;
}
return Math.max( getlongestSubstring(str, start+1, end, k, validString), getlongestSubstring(str, start, end-1, k, validString));
}
public static void main(String[] argc){
String str="asdfrttt";
int k =3;
HashSet<String> validString = new HashSet<String>();
System.out.println(getlongestSubstring(str,0, str.length(), k, validString));
int max = Integer.MIN_VALUE;
String LongestStr = new String();
for(String a: validString){
if(max<a.length())
{ max = a.length();
LongestStr = a;
}
}
System.out.println(LongestStr);
}
private static int uniqueCharCount(String str, int start, int end){
HashSet<Character> set= new HashSet<Character>();
for(int i=start; i<end; i++){
set.add(str.charAt(i));
}
return set.size();
}
private static int getlongestSubstring(String str, int start, int end, int k, HashSet<String> validString){
if(start <0 || end >str.length())
return 0;
if(k== uniqueCharCount(str,start,end)){
validString.add(str.substring(start,end));
return end-start;
}
return Math.max( getlongestSubstring(str, start+1, end, k, validString), getlongestSubstring(str, start, end-1, k, validString));
}
def substring(s):
"""
"aaaa" should return 1, "abcd" should return 4, "aabb" should return 2
:return length of the longest substring that does not contain repeated characters
:param s: string
:return: int
"""
d = {}
longest, currlen = 0, 0
idx = 0
start = end = 0
while idx < len(s):
if not s[idx] in d:
end = idx
else: # s[idx] in d
for i in range(start, d[s[idx]]):
d.pop(s[i])
start = d[s[idx]] + 1
currlen = idx - start + 1
d[s[idx]] = idx
longest = currlen if currlen > longest else longest
idx += 1
return longest
#python
def substring(s):
"""
"aaaa" should return 1, "abcd" should return 4, "aabb" should return 2
:return length of the longest substring that does not contain repeated characters
:param s: string
:return: int
"""
d = {}
longest, currlen = 0, 0
idx = 0
start = end = 0
while idx < len(s):
if not s[idx] in d:
end = idx
else: # s[idx] in d
for i in range(start, d[s[idx]]):
d.pop(s[i])
start = d[s[idx]] + 1
currlen = idx - start + 1
d[s[idx]] = idx
longest = currlen if currlen > longest else longest
idx += 1
return longest
char * k_long_substr( char* str, int k){
char* front = str, mid = str, end = str, front_out = str, end_out = str;
int num_ch = 1;
int char_table = 1 << (*str - ' a' );
int max = 0;
while( !end ){
if ( chars < k ){
end++;
char_table |= 1 << (*end - 'a');
} else {
front = ++mid;
}
if ( (end-front) > max ){
max = end-front;
front_out = front;
end_out = end;
}
}
++endout = '\0';
return front_out;
}
Two-pointer solution: start with the whole string and count the frequency of the characters and how many distinct ones there are(call it cnt). If cnt < k, then impossible. If cnt > k you need to shorten the string. So start with i=0 and j=length(s). Increase i only if s[i] will make the count of that character zero. If not then decrease j.
#include <map>
#include <cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
int t; cin >> t;
for(int _t=1; _t<=t; _t++){
string s; cin >> s;
int k; cin >> k;
map<char,int> F;
int cnt = 0;
for(int i=0; i<s.size(); ++i){
F[s[i]]++;
if(F[s[i]] == 1)
cnt++;
}
int i=0;
int j=s.size()-1;
while(i<j){
cout << i << " " << j << " cnt: " << cnt << endl;
if(cnt == k)
break;
if(cnt < k){
i = -1;
break;
}
if(F[s[i]] == 1){
F[s[i]]--;
cnt--;
i++;
}
else{
F[s[j]]--;
cnt -= (F[s[i]] == 0);
j--;
}
}
printf("Case #%d: ", _t);
if(i == -1)
cout << "impossible\n";
else
cout << s.substr(i,j-i+1) << endl;
}
}
Here's my solution for C++14. I went for readability since this question did not place requirements on the size of the string to search, nor the value of k.
#include <queue>
#include <string>
#include <iostream>
#include <unordered_set>
using namespace std;
int NumUniqueCharacters( const deque<char>& cur_substr )
{
static unordered_set<char> unique_chrs;
unique_chrs.clear();
for( auto itr = cur_substr.begin(); itr != cur_substr.end(); ++itr )
unique_chrs.insert( *itr );
return unique_chrs.size();
}
string KthLongestDistinctSubString( const string& str, const int& k )
{
deque<char> substr_buf;
string largest_substr;
for( const char& chr : str )
{
substr_buf.push_back( chr );
if( NumUniqueCharacters( substr_buf ) > k )
substr_buf.pop_front();
if( largest_substr.size() < substr_buf.size() )
largest_substr = string( substr_buf.begin(), substr_buf.end() );
}
return largest_substr;
}
int main()
{
string str_to_search;
int k;
cin >> str_to_search >> k;
cout << KthLongestDistinctSubString( str_to_search, k ) << endl;
return 0;
}
Solution in C++11
#include <iostream>
#include <string>
#include <set>
using namespace std;
int uniqueCharactersInString(const string& s)
{
set<char> unique;
for (const char& c : s)
if (unique.find(c) == unique.end())
unique.insert(c);
return unique.size();
}
string kLongestDistinctSubstring(const string& s, const int& k)
{
int follow = 0, //begining of the substring currently being evaluated
lead = k, //end of the substring currently being evaluated
beginIndex = 0, //instead of repeatedly storing the substring, we'll keep track of the indexes that it falls in
endIndex = k;
for (int i = 0; i <= s.length(); i++)
{
int tempLength = lead - follow;
if (uniqueCharactersInString(s.substr(follow, tempLength)) <= k)
{
if (tempLength > endIndex - beginIndex)
{
beginIndex = follow;
endIndex = lead;
}
lead++;
}
else
follow++;
}
return s.substr(beginIndex, endIndex - beginIndex);
}
int main(void)
{
string s;
int k;
cout << "String: ";
cin >> s;
cout << "Number of Unique characters: ";
cin >> k;
cout << kLongestDistinctSubstring(s, k) << endl;
system("Pause");
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class SubstringDistincyChars {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str="asdfrttt";
//String str="aaaasaaa";
int k=3;
SubstringDistincyChars sd = new SubstringDistincyChars();
String result = sd.getSubstring(str, k);
if(result.equals(str.substring(0, 1))){
System.out.println("Number of distinct characters in given strning is less than the given input");
}
else{
System.out.println("Max substring is "+result);
}
}
public String getSubstring(String s, int distinct){
char[] ch = s.toCharArray();
int n=1;
int ind =0;
String mainString = s.substring(0, 1);
String maxString = s.substring(0, 1);
List<Character> l = new ArrayList<Character>();
for(int i =0;i<ch.length;i++){
if(l.contains(ch[i])){
maxString = s.substring(0, i+1);
ind = i+1;
}else if(n<= distinct){
l.add(ch[i]);
maxString = s.substring(0, i+1);
n++;
ind = i+1;
}
}
if(n > distinct && maxString.length() > mainString.length()){
mainString = maxString;
}
if (mainString.length() < s.substring(ind,s.length()).length()){
mainString = getSubstring(s.substring(ind,s.length()), distinct);;
}
return mainString;
}
}
We can solve this using a 2 pointer approach
1. Maintain a sliding window using 'left' and 'right' variables
2. If the sliding window contains k distinct characters increment the right pointer. See if the substring in the window is the maximum seen till now
3. If the sliding window contains more than k distinct characters increment the left window
public static String longest(String str, int k) {
int left = 0;
int right = 0;
String max = "";
// maintain the latest position of each distinct element
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while (right <str.length()) {
if (map.size() > k) {
// process the left element
map.put(str.charAt(left), map.get(str.charAt(left))-1);
if (map.get(str.charAt(left)) == 0) {
map.remove(str.charAt(left));
}
left++;
} else {
// process the right element
if (map.containsKey(str.charAt(right))) {
map.put(str.charAt(right), map.get(str.charAt(right)+1));
if (right+1-left > max.length()) max = str.substring(left, right+1);
} else {
map.put(str.charAt(right), 1);
}
right++;
}
}
return max;
}
package practice.careercup;
import java.util.*;
import static java.util.stream.Collectors.joining;
public class LongestSubstringWithKDistinct {
public static void main(String[] args) {
String input = "aaaabbbbb";
int k = 2;
Set<Character> characterSet = new HashSet<>();
List<Character> characterList = new ArrayList<>();
for (Character character : input.toCharArray()) {
if (!characterSet.contains(character) && characterSet.size() == k){
System.out.println(characterList.stream().map(String::valueOf).collect(joining("")));
characterSet = new HashSet<>();
characterList = new ArrayList<>();
}
characterSet.add(character);
characterList.add(character);
}
if (characterSet.size() == k) {
System.out.println(characterList.stream().map(String::valueOf).collect(joining("")));
}
}
}
A C++ solution
The strategy here is to take advantage of two data structures to
accommodate our needs. The important data structure is the hashmap
(std::map in C++), which will lets us efficiently get duplicate counts and
unique letter counts in O(1) time.
The stringstream is the other structure used, though a queue may be
just as appropriate. The stringstream is expanded to the largest it can be,
then just stays that size, but only gets copied to the new max string if
the stringstream fits inside the required unique count.
std::string getMaxString(const char* input, size_t count, size_t k)
{
// Corner cases and edge cases
if (count <= k) return std::string(input);
if (k == 0) return std::string();
if (k == 1) return std::string(input).substr(0, 1);
// Map letter to num duplicates
std::map<char, int> hashmap;
std::string maxString;
std::stringstream currentString;
char trash;
while (input[0])
{
// Push the next character onto the queue
currentString << input[0];
// Ensure character exists and default to 0
hashmap.insert(std::make_pair(input[0], 0));
// Increment count of duplicated for current letter
++hashmap[input[0]];
// Shrink map if unique count hit cap
if (hashmap.size() > k)
{
// Pop the first character into a dummy variable
currentString >> trash;
std::map<char, int>::iterator itr = hashmap.find(trash);
--itr->second;
if (itr->second == 0)
hashmap.erase(itr);
}
// Set max string
if (hashmap.size() <= k &&
currentString.str().size() > maxString.size())
maxString = currentString.str();
}
return maxString;
}
func LongestSubstring(str string, uniqChars int) string {
if str == "" {
return ""
}
chrs := make(map[byte]interface{})
var substr, maxstr string
var i, j int = 0, 0
for j = 0; j <= len(str); j++ {
//fmt.Println("Substr: ", substr, " i = ", i, " j = ", j )
if j < len(str) {
chrs[str[j]] = nil // new char in set
}
if len(chrs) > uniqChars || j >= len(str) { // signal to check
if len(substr) > len(maxstr) {
maxstr = substr
}
//fmt.Println("len susbtr ", len(substr))
delete(chrs, substr[0])
// remove char from substring
for ; i < len(str) && str[i] == substr[0]; i++ {
}
}
if i < len(str) && j < len(str) {
substr = str[i : j+1]
}
//fmt.Println("after substr: ", substr)
}
return maxstr
}
private static String longestSubstring(String s, int maxChars){
String longest = "";
for (int startIdx = 0; startIdx < s.length(); startIdx++) {
StringBuffer sb = new StringBuffer();
int uniqChars = 0;
for (int i = startIdx; i < s.length(); i++) {
char c = s.charAt(i);
if (sb.indexOf(c+"") >= 0){
sb.append(c);
} else {
if (uniqChars < maxChars) {
sb.append(c);
uniqChars++;
} else {
break;
}
}
}
if (sb.length() > longest.length()){
longest = sb.toString();
}
}
return longest;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
This problem can be solved with TWO POINTERS that make a sliding window and a map to store occurrence of the distinct characters in the window.
public static String longestSubstringWithKDistinctChars(String s, int k) { int left = 0, right = 0; //create a window for substring(left, right + 1) Map<Character, Integer> distinctChars = new HashMap<>(); // store occurrence of chars in the window String max = ""; // the output while(right < s.length()) { char c = s.charAt(right); distinctChars.put(c, distinctChars.getOrDefault(c, 0) + 1); right++; if(distinctChars.size() == k) { //if window size == k, compare length of current substring with max if(right - left + 1 > max.length()) { max = s.substring(left, right + 1); //if current substring is longer, replace max with current } } while(distinctChars.size() == k + 1) { //if window size > k, discard the char on the left char toRemove = s.charAt(left); if(distinctChars.get(toRemove) == 1) { distinctChars.remove(toRemove); } else { distinctChars.put(toRemove, distinctChars.get(toRemove) - 1); } left++; } } return max; }This solution assumes that we only keep substrings with exactly 5 characters. So if the input string has less than k distinct characters, the return is "".
- aonecoding February 04, 2017