Facebook Interview Question Java Developers
Country: United States
My interpretation of the question is that we are asked to find a substring with at most k characters that may appear more than once (as opposed to any one character appearing more than k times). Is that not the case?
Hi @ChrisK, Thank you for your comment. I think you're totally right! So a proper solution should be:
var longestSubstring = function(s, k) {
var seen = {};
var slow = 0, fast = 0;
var max = 0;
while (fast < s.length) {
var c = s.charAt(fast);
if (c in seen) {
if (seen[c] == k) {
while (s.charAt(slow) != c) {
seen[s.charAt(slow)]--;
slow++;
}
slow++;
} else {
seen[c]++;
}
} else {
seen[c] = 1;
}
fast++;
if (fast - slow > max)
max = fast - slow;
}
return max;
}
I assume repeating characters may be different. E.g.
"abcdc" - 1 repeating char.
"abcdcb" - 2 repeating chars, no matter the repeating chars a different.
"abcdcbb" - 3 repeating chars.
#include <iostream>
#include <unordered_map>
using namespace std;
pair<int, int> LongestSubstring(string const &s, int k)
{
pair<int, int> out(-1, -1);
if (k >= s.size()) {
if (!s.empty()) {
out = pair<int, int>(0, s.size() - 1);
}
return out;
}
if (k > 0) {
int start = 0;
int max_size = 0;
unordered_map<char, int> seen;
int repeted_chars_count = 0;
for (int i = 0; i < s.size(); ++i) {
if (++seen[s[i]] > 1) {
++repeted_chars_count;
while (repeted_chars_count > k) {
if (--seen[s[start++]] != 0) {
--repeted_chars_count;
}
}
}
int size = i - start + 1;
if (size > max_size) {
max_size = size;
out = pair<int, int>(start, i);
}
}
}
return out;
}
int main() {
auto out = LongestSubstring("alblabljln", 2);
cout << out.first << " - " << out.second << "\n";
}
Here is my Javascript solution in O(n) time using O(n) space (n being the length of s):
var longestSubstring = function(s, k) {
var seen = {};
var slow = 0, fast = 0;
var max = 0;
while (fast < s.length) {
var c = s.charAt(fast);
if (c in seen) {
if (seen[c] == k) {
while (s.charAt(slow) != c) {
slow++;
}
slow++;
} else {
seen[c]++;
}
} else {
seen[c] = 1;
}
fast++;
if (fast - slow > max)
max = fast - slow;
}
return max;
}
Here is my O(n) time and O(n) space Javascript solution, using a fast and slow pointer:
var longestSubstring = function(s, k) {
var seen = {};
var slow = 0, fast = 0;
var max = 0;
while (fast < s.length) {
var c = s.charAt(fast);
if (c in seen) {
if (seen[c] == k) {
while (s.charAt(slow) != c) {
slow++;
}
slow++;
} else {
seen[c]++;
}
} else {
seen[c] = 1;
}
fast++;
if (fast - slow > max)
max = fast - slow;
}
return max;
}
Here is my approach O(n) time complexity and O(1) space:
1. Set two pointers (A and B) point at the beginning of the string.
2. Pointer A walks through the string and record the frequency of each character in count[26].
3. If the current character that pointer A points to appears more than K, save the substring between B (inclusive) and A (exclusive) if it is the longest substring so far.
4. Move the pointer B and subtract the pointing character from count[26] until we get the frequencies of all characters in count[26] no more than K.
5. Repeat the process from step 2 until it reaches the end of the string.
//Assume given string is all low case between [a-z]
public String longestSubstring(String str, int K)
{
int A = 0;
int B = 0;
int[] count = new int[26];
int longestLen = 0;
String result;
for(;A<str.length();A++)
{
if(++count[str.charAt(A)-'a'] > K)
{
if(longestLen < A-B)
{
result = str.substring(B,A);
}
for(;B<A;B++)
{
if(--count[str.charAt(B)-'a'] == K)
{
B++;
break;
}
}
}
}
//indicates none of the characters in given string appears more than K
if(result == null) return str;
return result;
}
Here's my implementation in C.
Walking the string from left to right, you compute the length of the longest substring ending at each character. You then simply pick the substring ending at the character with the biggest substring length. Compiled and tested at interviewing.io
Sample output:
aacdbbeb, k = 2. Output = aacdbbeb
alblabljln, k = 1. Output = ablj
alblabljln, k = 2. Output = alblab
#include <stdio.h>
#include <string.h>
void LongestSubstringWorker (char *string, unsigned int factor,
unsigned int *maxlen,
unsigned int *maxindex,
unsigned int currindex) {
unsigned int count[256];
unsigned int len[strlen(string)];
unsigned int i,j;
for (i = 0; i < 256; i++) {
count[i] = 0;
}
for (i = 0; i < strlen(string); i++) {
len[i] = 1;
}
count[(unsigned char)string[0]] = 1;
for (i = 1; i < strlen(string); i++) {
count[(unsigned char)string[i]]++;
if (count[(unsigned char)string[i]] <= factor) {
len[i] = len[i - 1] + 1;
if (len[i] > *maxlen) {
*maxlen = len[i];
*maxindex = i + currindex;
}
} else {
for (j = 0; j < i; j++) {
if (string[j] == string[i]) {
LongestSubstringWorker (&string[j + 1], factor,
maxlen, maxindex, j + 1 + currindex);
return;
}
}
}
}
}
void LongestSubstring (char *string, unsigned int factor) {
unsigned int maxlen;
unsigned int maxindex;
unsigned int i;
if (string == NULL) {
return;
}
maxlen = 1;
maxindex = 0;
LongestSubstringWorker(string, factor, &maxlen, &maxindex, 0);
for (i = maxindex - (maxlen - 1); i <= maxindex; i++) {
printf("%c", string[i]);
}
printf("\n");
}
int main() {
LongestSubstring("alblabljln", 1);
return 0;
}
def longestSubstringRepeating(string,k):
if not string or k==0:
return 0
max_len, start = 0, 0
dic= dict()
for idx, char in enumerate(string):
dic[char] = dic.get(char,0) + 1
while dic[char]>k:
dic[string[start]] = dic[string[start]]-1
start = start+1
max_len = max(max_len, idx-start+1)
return max_len
@Raphael: The approach is good, I think the code has an issue: when moving the "slow" pointer shouldn't we decrement the element count that leaves the window (not only the one that has been seen more than k times)
while (s.charAt(slow) != c) { seen[s.charAt(slow)]--; slow++; }e.g.
- Chris November 27, 20171,2,3,2,2,1,1,5,6,7,8, k = 2 --> 3,2,2,1,1,5,6,7,8