## Google Interview Question for Software Developers

Country: United States

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

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 "".

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

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;
}``````

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

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;

}``````

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

``````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))
}``````

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

``````#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;
}``````

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

``````#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;
}``````

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

``````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){
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();

}

}``````

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

``````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){
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();

}

}``````

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

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)``````

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

``````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]))
{
}

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);
}``````

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

``````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;
}``````

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

``````#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)``````

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

``````!/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])

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

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``````

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

``````#!/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])

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

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``````

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

test

``foo=bar``

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

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++){
}
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)){
return end-start;
}
return Math.max( getlongestSubstring(str, start+1, end, k, validString), getlongestSubstring(str, start, end-1, k, validString));
}

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

``````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++){
}
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)){
return end-start;
}
return Math.max( getlongestSubstring(str,  start+1, end, k, validString), getlongestSubstring(str, start, end-1, k, validString));
}``````

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

``````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``````

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

``````#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``````

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

``````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;
}``````

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

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;
}

}``````

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

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;
}``````

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

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;
}

}
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;
}``````

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

``````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){
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;
}
}``````

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

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;
}``````

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

``````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<>();
}

}

if (characterSet.size() == k) {
System.out.println(characterList.stream().map(String::valueOf).collect(joining("")));
}
}
}``````

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

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;
}``````

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

``````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
}``````

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

``````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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{ #include <stdio.h> #include <string.h> char *lss(char *a, int k) { char *f[100]; char *p, *c, *sp; int i, l, n = 0, mc = 0; // scan string to pointers to n differing char types and endchar for (c = a; *c; *c++) { if (c == a) { f[n++] = a; } else { if (*p != *c) { f[n++] = c; } } p = c; } f[n] = c; // iterate thru chartypes measuring pointer deltas taking max of it if (n<=k) { return a; } else { for (i=k; i<n; i++) { if (i<=k) { l = f[i+1] - f[0]; } else { l = f[i+1] - f[k]; } if (l > mc) { mc = l; sp = f[i-k+1]; } } return strndup(sp, mc); // return max chars from its start pointer } } int main() { printf("%s\n", lss("aaaabbbb", 2)); printf("%s\n", lss("asdfrttt", 3)); } )))

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.