## Facebook Interview Question for Software Developers

• 1

Country: United States
Interview Type: In-Person

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

O(n) time and O(1) space solution assuming a constant size alphabet set of the characters in the string. The idea is to stretch a sliding window until we find all characters. Once we find all the characters then we either slide the window if not reached the end of string or we can shrink the window as long as we all characters matches in the shrunk window.

//O(1) match between two histogram due to constant size alphabet i.e. 256
private static int countMatches(int[] textHist, int[] patHist){
int match = 0;
for(int i = 0; i< 256; i++){
if(patHist[i] > 0 && textHist[i] > 0){
match++;
}
}

return match;
}

public static String minLenSubStringWithAllChars(String str, Set<Character> chars){
int[] textHist = new int[256];
int[] patHist = new int[256];
int start = 0;
int end = 0;
int minLen = Integer.MAX_VALUE;
int bestStart = 0;
int bestEnd = 0;

//prepare the initial window of size of the char set
for(char c: chars){
textHist[str.charAt(end)]++;
patHist[c]++;
end++;
}

while(start < str.length()){
int matches = countMatches(textHist, patHist);
//if current window doesn't contain all the characters
//then strech the window to right upto the end of string
if(matches < chars.size() && end < str.length()){
//strech window
textHist[str.charAt(end)]++;
end++;
}
//if current window contains all the characters with frequency
//at least one then we have the freedom to shrink the window
//from front.
else if(matches >= chars.size()){
//as current window contains all character so update minLen
if(end-start < minLen){
minLen = end-start;
bestStart = start;
bestEnd = end;
}
//shrink window
textHist[str.charAt(start)]--;
start++;
}
//if current window doesn't cntains all chars
//but we can't strech the window anymore then break
else{
break;
}
}

return str.substring(bestStart, bestEnd);
}

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

wonderful and elegant solution. Thumbs up!

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

doesn't it looks like Kadane's algorithm?

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

@dhs, yes . it is a modified Kadane's algorithm.

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

Very elegant and indeed a great solution. :D

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

I decided to use the dynamic programming approach for this problem where we look for the shortest sub-string in S[i:] that contains element in a A where A is a sub-string of T. Also, we keep track of its initial index.
Note that this approach is O(N) given that the number of possible sub-strings of T is constant and small compare to N.
Complexity: O(N)

Program in Python:

def permute(alphabet):
Perm=[]
L=len(alphabet)
for j in range(L):
p=[alphabet[j]]
Perm.append(p)
for  i in range(j+1,L):
e=p[:]
e.extend(alphabet[i:])
Perm.append(set(e))
e=[]
for  i in range(j+1,L-1):
e=p[:]
e.append(alphabet[i])
Perm.append(set(e))
e=[]
return Perm
S=raw_input()
alphabet=raw_input()
N=len(S)
L=len(alphabet)
#keep track of length of substring
dp={}
#keep track of the beginning index of substring
index={}
Perm=permute(alphabet)
for A in Perm:
dp[(N,tuple(A))]=0
index[(N,tuple(A))]=N
dic=set([])
for i in range(N-1,-1,-1):
if S[i]in set(alphabet):
dic=dic.union(set(S[i]))
choice=[]
choice=permute(list(dic))
for A in Perm:
if A in choice:
if S[i] in A:
B=list(A)[:]
B.pop(B.index(S[i]))
if len(B)==0:
dp[(i,tuple(A))]=1
index[(i,tuple(A))]=i
elif dp[(i+1,tuple(A))] < dp[(i+1,tuple(B))]+index[(i+1,tuple(B))]-i :
dp[(i,tuple(A))]=dp[(i+1,tuple(A))]
index[(i,tuple(A))]=index[i+1,tuple(A)]
else:
dp[(i,tuple(A))]=dp[(i+1,tuple(B))]+index[(i+1,tuple(B))]-i
index[(i,tuple(A))]=i
else:
dp[(i,tuple(A))]=dp[(i+1,tuple(A))]
index[(i,tuple(A))]=index[i+1,tuple(A)]
elif A==[]:
dp[(i,tuple(A))]=0
index[(i,tuple(A))]=i
else:
dp[(i,tuple(A))]=float('infinity')
index[(i,tuple(A))]=i

min_len_substring=dp[(0,tuple(set(alphabet)))]
A=tuple(set(alphabet))
print str(dp[(0,A)])
print str(S[index[(0,A)]:index[(0,A)]+min_len_substring])

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

You have needlessly complicated a simple soln. This can be done in less than 10 lines

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

This is insanely complicated for a solution to this problem. I'm also pretty sure creating all the permutations is not very efficient.

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

quite complicated. Could you please explain?

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

Take 2 arrays, isReq[256] and isFound[256] which tells the frequency of each character in S and while parsing the string S, the frequency of each character that has found yet.
Also, keep a counter which tells when a valid window is found.
Once a valid window is found, we can shift the window (towards right) maintaining the given invariant of the question.

Complexity: O(N)

Program in C++:

void findMinWindow(const char *S, const char *T, int &start, int &end){
int SLen = strlen(S);
int TLen = strlen(T);

// Declare 2 arrays which keep tab of required & found frequency of each char in T
int isReq[256] ;
int isFound[256];
int count = 0; //For valid window

int minWindow = INT_MAX;

//Prepare the isReq[] array by parsing the T
for(int i=0;i<TLen;i++){
isReq[T[i]]++;
}

//Let's start parsing the S now; Take 2 pointers: i and j - both starting at 0
int i=0, j=0;

//Keep moving j forward, keep i fixed till we get a valid window
for(c=j;c<SLen;c++){
//Check if the character read appears in T or not
if(isReq[S[c]] == 0){
//This character does not appear in the T; skip this
continue;
}
//We have this character in the T, lets increment isFound for this char
isFound[S[c]]++;

//increment the count if this character satisfies the invariant
if(isFound[S[c]] <= isReq[S[c]]){
count++;
}

//Did we find a valid window yet?
if(count == TLen){
//A valid window is found..lets see if we can do better from here on
//better means: increasing i to reduce window length while maintaining invariant
while(isReq[s[i]] == 0 || isFound[s[i]] > isReq[s[i]]){
//Either of the above 2 conditions means we should increment i; however we
// must decrease isFound for this char as well.
//Hence do a check again
if(isFound[s[i]] > isReq[s[i]]){
isFound[s[i]]--;
}
i++;
}

// Note that after the while loop, the invariant is still maintained
// Lets check if we did better
int winLength = j-i+1;
if(winLength < minWindow){
//update the references we got
begin = i;
end = j;
//Update new minimum window lenght
minWindow = winLength;
}
} //End of if(count == TLen)
} //End of for loop
}

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

The way I see it, T="aab" is same as T="ab", don't you agree?

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

Corrected a few bugs .Here is the running C version of your code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int findMinWindow(const char *S, const char *T,int* begin,int* end);

void main()
{

int begin=0,end =0;
int minLength=0;
const char *T="abc";
minLength=findMinWindow(S,T,&begin,&end);

printf("minLength=%d,begin=%d,end=%d \n",minLength,begin,end);
printf("\nPrinting Min Sub String\n");

for(int i=0;i<minLength;i++)
printf("%c",S[begin+i]);

}

int findMinWindow(const char *S, const char *T,int * begin,int* end ){
int SLen = strlen(S);
int TLen = strlen(T);

// Declare 2 arrays which keep tab of required & found frequency of each char in T
int isReq[256] ;
int isFound[256];
memset(isReq,'0',sizeof(isReq));
memset(isFound,'0',sizeof(isFound));

int count = 0; //For valid window

int minWindow = INT_MAX;

//Prepare the isReq[] array by parsing the T
for(int i=0;i<TLen;i++){
isReq[T[i]]++;
}

//Let's start parsing the S now; Take 2 pointers: i and j - both starting at 0
int i=0, j=0;

//Keep moving j forward, keep i fixed till we get a valid window
for(int c=j;c<SLen;c++,j++){
//Check if the character read appears in T or not
if(isReq[S[c]] == 0){
//This character does not appear in the T; skip this
continue;
}
//We have this character in the T, lets increment isFound for this char
isFound[S[c]]++;

//increment the count if this character satisfies the invariant
if(isFound[S[c]] <= isReq[S[c]]){
count++;
}

//Did we find a valid window yet?
if(count == TLen){
//A valid window is found..lets see if we can do better from here on
//better means: increasing i to reduce window length while maintaining invariant
while(isReq[S[i]] == 0 || isFound[S[i]] > isReq[S[i]]){
//Either of the above 2 conditions means we should increment i; however we
// must decrease isFound for this char as well.
//Hence do a check again
if(isFound[S[i]] > isReq[S[i]]){
isFound[S[i]]--;
}
i++;
printf("\nIn while loop %c,i=%d,S[c]=%c,c=%d",S[i],i,S[c],c);
}

// Note that after the while loop, the invariant is still maintained
// Lets check if we did better
int winLength = j-i+1;
printf("\nwinLength=%d \n",winLength);

if(winLength < minWindow){
//update the references we got
*begin = i;
*end = j;
//Update new minimum window length
minWindow = winLength;
// printf("\nminWindow=%d",minWindow);
}
} //End of if(count == TLen)
} //End of for loop
return minWindow;
}

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

@Mailman: Your code is correct. But I want to mention that your code/logic can be reduced as the question already says "Unique elements in T".

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

how is this code run in O(n)?

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

why is O(n)? Isn't in non-linear?

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

#include<iostream>
#include<map>
using namespace std;

#define R 256 // if ASCII is assumed otherwise 2^16 of unicode

void findIt(string s, string t)
{
int n=s.length();
int m=t.length();
if(n==0 || m==0)
return;
bool *f=new bool[R];
memset(f, false, sizeof(bool) * R);

for(int i=0;i<m;i++)
f[t[i]]=true;

int *ff=new int[R];
memset(ff, 0, sizeof(int)*R);
int *fff=new int[n];
memset(fff,0,sizeof(int)*n);

for(int i=0;i<n;i++)
{
if(f[s[i]])
{
ff[s[i]]++;
fff[i]=ff[s[i]];
}
}

int j,b,e,mx=INT_MAX;
for(int i=0;i<n;i++)
{
if(fff[i]==0)
continue;
else
{
j=i+1;
int cnt=1;
while(cnt!=m)
{
if(fff[j++]==fff[i])
cnt++;
}
if(j-i-1<mx)
{
b=i;
e=j-1;
mx=j-i;
}
if(j>=R)
break;
i=j;
}
}
delete [] f;
delete [] ff;
delete [] fff;

cout<<b<<"  "<<e<<"  "<<mx<<endl;

}

int main()
{
string t="abc";
findIt(s,t);
cout<<endl;
getchar();
return 0;
}

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

There is a problem with the last for loop of this method and here's the fix for it (apologies for careless mistake):

for(int i=0;i<n;i++)
{
if(fff[i]==0)
continue;
else
{
j=i+1;
int cnt=1;
while(j<n && cnt!=m)
{
if(fff[j++]==fff[i])
cnt++;
}
if(cnt == m && j-i-1<mx)
{
b=i;
e=j-1;
mx=j-i;
}
i=j;
}
}

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

#include<iostream>
#include<map>
using namespace std;

#define R 256 // if ASCII is assumed otherwise 2^16 of unicode

void findIt(string s, string t)
{
int n=s.length();
int m=t.length();
if(n==0 || m==0)
return;
bool *f=new bool[R];
memset(f, false, sizeof(bool) * R);

for(int i=0;i<m;i++)
f[t[i]]=true;

int *ff=new int[R];
memset(ff, 0, sizeof(int)*R);
int *fff=new int[n];
memset(fff,0,sizeof(int)*n);

for(int i=0;i<n;i++)
{
if(f[s[i]])
{
ff[s[i]]++;
fff[i]=ff[s[i]];
}
}

int j,b,e,mx=INT_MAX;
for(int i=0;i<n;i++)
{
if(fff[i]==0)
continue;
else
{
j=i+1;
int cnt=1;
while(cnt!=m)
{
if(fff[j++]==fff[i])
cnt++;
}
if(j-i-1<mx)
{
b=i;
e=j-1;
mx=j-i;
}
if(j>=R)
break;
i=j;
}
}
delete [] f;
delete [] ff;
delete [] fff;

cout<<b<<"  "<<e<<"  "<<mx<<endl;

}

int main()
{
string t="abc";
findIt(s,t);
cout<<endl;
getchar();
return 0;
}

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

php solution

function shortest_has_all(\$string, \$keys) {
\$keys_last_location = [];
foreach (\$keys as \$key) {
\$keys_last_location[\$key] = PHP_INT_MAX;
}

\$keys_found = [];
\$min_key_location = PHP_INT_MAX;
\$shortest = PHP_INT_MAX;
\$shortest_sequence = [-1,-1];

\$string = str_split(\$string);
foreach (\$string as \$index => \$char) {
if (!in_array(\$char, \$keys)) {
continue;
}

\$keys_found[\$char] = true;

\$keys_last_location[\$char] = \$index;

\$min_key = get_min_key(\$keys_last_location, \$keys);
if (\$min_key == \$char) {
\$min_key_location = \$keys_last_location[\$min_key];
}

if (count(\$keys_found) == count(\$keys)) {
if (\$index - \$min_key_location < \$shortest_sequence) {
\$shortest_sequence = [\$min_key_location, \$index];
}
}
}

return \$shortest_sequence;
}

function get_min_key(\$keys_locations, \$keys) {
\$min_location = PHP_INT_MAX;
\$min_key = null;
foreach (\$keys as \$key) {
if (count(\$keys_locations[\$key]) > 0) {
if (\$keys_locations[\$key][0] < \$min_location) {
\$min_location = \$keys_locations[\$key][0];
\$min_key = \$key;
}
}
}
return \$min_key;
}

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

#include <iostream>
#include <string>
#include <list>
using namespace std;
int main()
{
list <int> buf;
string sub="aet";
string s="qkefqkbfljsaeyuecvgaet";
int l=0,r=0,j=0,flag=0;
for (int i=0; i<s.size(); i++)
{
for (int j=0;j<sub.size();j++)
{
if(s[i]==sub[j])
{
buf.push_back(i);
while (s[i]==s[buf.front()] && i!=buf.front())
buf.pop_front();
break;
}
}
}
cout<<s.substr(buf.front(),buf.back());
}

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

def foo_2(S, T):
# input checks
if len(S) == 0:
if len(T) == 0:
return ''
else:
return None
if len(S) < len(T):
return None
# recure
if set.intersection(set(S),set(T)) == set(T):
front = foo_2(S[:-1], T)
if not front == None:
return front
end = foo_2(S[1:], T)
if not end == None:
return end
return S
else:
return None

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

It is enough to walk the string and look for runs of characters. Just remember the shortest string found until now and output the same at the end. This is O(NK) where N is length of the string and K is length of the set to be found.

final String toFind = "abc";

int leastStrStartPos = -1;
int leastStrLength = Integer.MAX_VALUE;

/*
walk the string until you get the full set.
update least* if the substring length is smaller than known.
Restart the walk from the next position to ensure there is no shorter string that follows.
You can ignore the strings that include the prev character because that would've been caught
in the previous run itself.
*/

// you need not do the meta walk once the remaining string size is < the
// toFind Size.
for (int i = 0; i < givenStr.length() - toFind.length() + 1; i++) {
if (-1 != toFind.indexOf(givenStr.charAt(i))) {
// start the walk and look for remaining characters.
String remainingToFind = toFind.replace(
String.valueOf(givenStr.charAt(i)), "");
for (int j = i + 1; j < givenStr.length()
&& remainingToFind.length() > 0; j++) {
if (-1 != remainingToFind.indexOf(givenStr.charAt(j))) {
remainingToFind = remainingToFind.replace(
String.valueOf(givenStr.charAt(j)), "");
if (remainingToFind.isEmpty()) {
// found the substring from i to j.
if (leastStrLength > j - i + 1) {
leastStrLength = j - i + 1;
leastStrStartPos = i;
}
break;
}
}
}
if (!remainingToFind.isEmpty()) {
// some characters are missing. We can terminate the outer
// loop too
break;
}
if (leastStrLength == toFind.length()) {
break;// min possible is found
}
}
}

System.out.println("Given String: " + givenStr);
System.out.println("To find set: " + toFind);
if (leastStrStartPos != -1) {
System.out.println("Found at: " + leastStrStartPos + ". Length: "
+ leastStrLength + ". SubString: "
+ givenStr.substring(leastStrStartPos,
leastStrStartPos + leastStrLength));
} else {
System.out.println(
"Given string doesn't have all the characters we were looking for!");
}

Output:

To find set: abc
Found at: 9. Length: 4. SubString: banc

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

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;

// If N is the length of t and M is the length of t and assuming M < N
// Time: O(N log M)
// Space: O(M)
public class MinConSub
{
public static String minSubString(String s, String t)
{
if (s == null || t == null || t.length() == 0)
{
return null;
}
Set<Character> target = new HashSet<>();
for (char c : t.toCharArray())
{
}
PriorityQueue<Integer> q = new PriorityQueue<>();
Map<Character, Integer> index = new HashMap<>();
String min = null;
for (int i = 0; i < s.length(); i++)
{
char c = s.charAt(i);
if (target.contains(c))
{
if (index.containsKey(c))
{
q.remove(index.get(c));
}
index.put(c, i);
if (index.size() == target.size())
{
int j = q.peek();
if (min == null || min.length() > 1 + i - j)
{
min = s.substring(j, i + 1);
}
}
}
}
return min;
}

public static void main(String[] args)
{
if (args.length < 2)
{
System.err.println("args: [s] [t]");
System.exit(1);
}
System.out.println(minSubString(args[0], args[1]));
}
}

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

R

t <- 'abc'
t <- strsplit(t,'')[[1]]
sz <- 2
test <- FALSE
while(test == FALSE){
for(i in 1:(nchar(s)-sz)){
s1 <- strsplit(substr(s,i,i+sz),'')[[1]]
if(sum(t %in% s1) == 3) {
test <- TRUE
cat(s1)
}
}
sz <- sz + 1
}

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

import java.util.HashSet;

public class Longestmatch {

public static void main(String[] args) {

}

public static String match(String input, String sub)
{
if(input.length()<sub.length()) return null;
boolean[] set= new boolean [256];
int start=0,end=0,maxlen=0;
HashSet<Character> map = new HashSet <Character>();

for(int p=0; p<set.length;p++)
{
set[p]= false;
}
for(int i=0; i<sub.length();i++)
{
set[(int)sub.charAt(i)]= true;
System.out.println("sub char="+sub.charAt(i)+","+(int)sub.charAt(i));
}

boolean reset= true;
for(int j=0,k=0; j<input.length();j++,k++)
{	System.out.println(input.charAt(j));
if(reset==true)
{ 	map.clear();
start=j;end=j;
}
if(set[(int)input.charAt(j)]== true)
{
System.out.println("char match="+input.charAt(j));
reset=false;
}
end++;
if(map.size()==sub.length())
{	System.out.println("map full");
if( maxlen<j)
{	maxlen=j;
}
reset=true;
}
}
System.out.println("start="+start+",end="+end);
if(maxlen>=sub.length())
return input.substring(start,end);
else
return null;
}
}

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

import java.util.HashSet;

public class Longestmatch {

public static void main(String[] args) {

}

public static String match(String input, String sub)
{
if(input.length()<sub.length()) return null;
boolean[] set= new boolean [256];
int start=0,end=0,maxlen=0;
HashSet<Character> map = new HashSet <Character>();

for(int p=0; p<set.length;p++)
{
set[p]= false;
}
for(int i=0; i<sub.length();i++)
{
set[(int)sub.charAt(i)]= true;
System.out.println("sub char="+sub.charAt(i)+","+(int)sub.charAt(i));
}

boolean reset= true;
for(int j=0,k=0; j<input.length();j++,k++)
{	System.out.println(input.charAt(j));
if(reset==true)
{ 	map.clear();
start=j;end=j;
}
if(set[(int)input.charAt(j)]== true)
{
System.out.println("char match="+input.charAt(j));
reset=false;
}
end++;
if(map.size()==sub.length())
{	System.out.println("map full");
if( maxlen<j)
{	maxlen=j;
}
reset=true;
}
}
System.out.println("start="+start+",end="+end);
if(maxlen>=sub.length())
return input.substring(start,end);
else
return null;
}
}

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

import java.util.HashSet;

public class Longestmatch {

public static void main(String[] args) {

}

public static String match(String input, String sub)
{
if(input.length()<sub.length()) return null;
boolean[] set= new boolean [256];
int start=0,end=0,maxlen=0;
HashSet<Character> map = new HashSet <Character>();

for(int p=0; p<set.length;p++)
{
set[p]= false;
}
for(int i=0; i<sub.length();i++)
{
set[(int)sub.charAt(i)]= true;
System.out.println("sub char="+sub.charAt(i)+","+(int)sub.charAt(i));
}

boolean reset= true;
for(int j=0,k=0; j<input.length();j++,k++)
{	System.out.println(input.charAt(j));
if(reset==true)
{ 	map.clear();
start=j;end=j;
}
if(set[(int)input.charAt(j)]== true)
{
System.out.println("char match="+input.charAt(j));
reset=false;
}
end++;
if(map.size()==sub.length())
{	System.out.println("map full");
if( maxlen<j)
{	maxlen=j;
}
reset=true;
}
}
System.out.println("start="+start+",end="+end);
if(maxlen>=sub.length())
return input.substring(start,end);
else
return null;
}
}

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

An O(N) solution

#define GET_CHAR_IDX(c) c

#define GET(x) source[x]

string minWindow(const string &source, const string &target)
{
deque<int> Q;
vector<int> AlltargetLetters(256,0);
vector<int> targetFound(256,0);
int MinWindow = INT_MAX;
int MinWindowStart = INT_MIN;
int MinWindowEnd = INT_MIN;
int MaxLetterFound = 0;

int start = 0;
int Laststart =0 ;

for(auto c : target)
{
AlltargetLetters[GET_CHAR_IDX(c)]++;
}

while(start < source.size())
{
if(AlltargetLetters[GET_CHAR_IDX(GET(start))] > 0)
{
Q.push_back(start);
targetFound[GET_CHAR_IDX(GET(start))]++;

if(targetFound[GET_CHAR_IDX(GET(start))] <= 		AlltargetLetters[GET_CHAR_IDX(GET(start))])
{
MaxLetterFound++;
}
}
else
{
if(Q.empty())
{
Laststart++;
}
}

while(MaxLetterFound == target.size())
{
int next = Q.front();
Q.pop_front();

Laststart = next;

if(targetFound[GET_CHAR_IDX(GET(next))] == AlltargetLetters[GET_CHAR_IDX(GET(next))])
{
MaxLetterFound--;
}

targetFound[GET_CHAR_IDX(GET(next))]--;

if(MinWindow > start - Laststart + 1)
{
MinWindow = start - Laststart + 1;
MinWindowStart = Laststart;
MinWindowEnd = start;
}
}

start++;
}

if(MinWindowStart == INT_MIN) return "";

return (source.substr(MinWindowStart,MinWindowEnd - MinWindowStart + 1));
}

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

O(n) time, O(n) space complexity. Use double linked-list.
Analysis: allenlipeng47.com/PersonalPage/index/view/198/nkey
Check my code: github.com/allenlipeng47/algorithm/blob/master/src/main/java/com/pli/project/algorithm/array/MinConsecutiveSubStr.java

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

start from length of t and iterate through s with the same length. Increment until you hit the string with the string that contains t.

public string Result(string s, string t)
{
// get combo of substring s with >= length of t
int tLength = t.Length;
int sLength = s.Length;
if (tLength > sLength || string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
return string.Empty;

var tArray = t.ToCharArray();
List<char> tList = tArray.ToList();

int startLength = tLength;
// work from smallest length to largest
while (startLength <= sLength)
{
for (int i = 0; i <= sLength - startLength; i++)
{
var testString = s.Substring(i, startLength);

// check if testString contains all of tArray
// find strings that contains t
var listToCheck = tList.ToList();
var validString = IsValidString(testString.ToCharArray(), listToCheck);
if (validString)
return testString;
}
startLength++;
}

return string.Empty;
}

public bool IsValidString(char[] check, List<char> valid)
{
foreach (var c in check)
{
if (valid.Contains(c))
valid.Remove(c);

if (valid.Count == 0)
return true;
}
return false;
}

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

c#

public string Result(string s, string t)
{
// get combo of substring s with >= length of t
int tLength = t.Length;
int sLength = s.Length;
if (tLength > sLength || string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
return string.Empty;

var tArray = t.ToCharArray();
List<char> tList = tArray.ToList();

int startLength = tLength;
// work from smallest length to largest
while (startLength <= sLength)
{
for (int i = 0; i <= sLength - startLength; i++)
{
var testString = s.Substring(i, startLength);

// check if testString contains all of tArray
// find strings that contains t
var listToCheck = tList.ToList();
var validString = IsValidString(testString.ToCharArray(), listToCheck);
if (validString)
return testString;
}
startLength++;
}

return string.Empty;
}

public bool IsValidString(char[] check, List<char> valid)
{
foreach (var c in check)
{
if (valid.Contains(c))
valid.Remove(c);

if (valid.Count == 0)
return true;
}
return false;
}

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

O(n) solution

public static void main(String[] args) {
String T = "abc";

System.out.println(smallestSubstring(S,T));
}

public static String smallestSubstring(String S, String T) {

Map<Character, Integer> map = new HashMap<Character, Integer>();
int bestResultLength = Integer.MAX_VALUE;
String bestSubstring = "";

for (Character c : T.toCharArray()) {
map.put(c, -1);
}

for (int i = 0; i < S.length(); i++) {
if (map.containsKey(S.charAt(i))) {
map.put(S.charAt(i), i);
String interimResult = substring(S, map);
if (interimResult != null && interimResult.length() < bestResultLength) {
bestSubstring = interimResult;
bestResultLength = interimResult.length();
}
}
}
return bestSubstring;
}

public static String substring(String S, Map<Character, Integer> map) {
ArrayList<Integer> list = new ArrayList<Integer>(map.values());
for (Integer i : list) {
if (i == -1) return null;
}
Collections.sort(list);
return S.substring(list.get(0), list.get(list.size() - 1) + 1);
}

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

#include<string>
#include<iostream>
#include<vector>
using namespace std;

int main()
{
vector <int> buf;
string sub="abc";
string bkp=sub;
string min_string = s;
for (int i=0; i<s.size(); i++)
{
for (int j=0; j<sub.size(); j++)
{
if (sub[j]==s[i])
buf.push_back(i);
}
}
for (int i=0; i<buf.size(); i++)
{
bkp=sub;
for (int j=i; j<buf.size()-bkp.size()+1; j++)
{
for (int k=0; k<bkp.size(); k++)
{
if (bkp[k]==s[buf[j]])
{
bkp.erase(k,1);
break;
}
}
if (bkp.size()==0)
{
if (min_string.size() - buf[j]+buf[i]-1>0)
{
min_string = s.substr(buf[i],buf[j]-buf[i]+1);
}
break;
}
}
}
cout<<min_string<<endl;
}

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

string t = "abc";

var t0 = t.Trim();

var candidate = "";
List<string> options = new List<string>();
string result = s;
int pinIndex = 0;

for(int currentIndex = 0; currentIndex < s.Length; currentIndex++)
{
char r = s[currentIndex];

if (t.Contains(r))
{
t = t.Replace(r, ' ').Trim();
if(candidate == "")
pinIndex = currentIndex;
candidate += r;
}
else if (candidate != "")
{
candidate += r;
}

if (t.Length == 0)
{
t = t0;
if (result.Length > candidate.Length)
result = candidate;
candidate = "";
currentIndex = pinIndex;
}
}

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

string t = "abc";

var t0 = t.Trim();

var candidate = "";
List<string> options = new List<string>();
string result = s;
int pinIndex = 0;

for(int currentIndex = 0; currentIndex < s.Length; currentIndex++)
{
char r = s[currentIndex];

if (t.Contains(r))
{
t = t.Replace(r, ' ').Trim();
if(candidate == "")
pinIndex = currentIndex;
candidate += r;
}
else if (candidate != "")
{
candidate += r;
}

if (t.Length == 0)
{
t = t0;
if (result.Length > candidate.Length)
result = candidate;
candidate = "";
currentIndex = pinIndex;
}

}

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

string t = "abc";

var t0 = t.Trim();

var candidate = "";
List<string> options = new List<string>();
string result = s;
int pinIndex = 0;

for(int currentIndex = 0; currentIndex < s.Length; currentIndex++)
{
char r = s[currentIndex];

if (t.Contains(r))
{
t = t.Replace(r, ' ').Trim();
if(candidate == "")
pinIndex = currentIndex;
candidate += r;
}
else if (candidate != "")
{
candidate += r;
}

if (t.Length == 0)
{
t = t0;
if (result.Length > candidate.Length)
result = candidate;
candidate = "";
currentIndex = pinIndex;
}
}

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

C++ implementation. O(|S|) solution. See explanation below.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string minSubstring(string S, string T) {
unordered_map<char, int> charS;
for(int i=0; i<S.length(); ++i) { //|S| steps
++charS[S[i]];
}

for(int j=0; j<T.length(); ++j) { //|T|<=|S| steps assuming T shorter than S
--charS[T[j]];
if(charS[T[j]]<0) {
return "No substring found";
}
}

int startIndex=0;
int endIndex=(int) S.length()-1;

// these two while loops: at most |S| steps; unordered_map maeans constant time retrieval
while(charS[S[startIndex]]>=1) {
--charS[S[startIndex]];
++startIndex;
}

while(charS[S[endIndex]]>=1) {
--charS[S[endIndex]];
--endIndex;
}

return S.substr(startIndex, endIndex);
}

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

- Run through String T and create a map with all characters
- Run through String S and add count of the characters in map
- Run through beginning of S with idx i and move ahead until count of a char in map is 1. Then move backwards with idx j until a char in map reaches 1 (decrement count if not 1).
- Save substring S(i,j)
Repeat above steps but in this case first find j' and then i'
- Save substring S(i',j')
Result is min of [S(i,j) , S(i',j') ]

// Complexity Time : O(2T+4S)=O(T+S) space : O(T)

public class MinimalSubstringContainingChars {

public static String findMinimalSubstring(String S, String T) {
char[] tchars = T.toCharArray();
char[] schars = S.toCharArray();
HashMap<Character, Integer> map = new HashMap<>();
for(char c : tchars) {
map.put(c, 0);
}
for(char c : schars) {
Integer val = map.get(c);
if(val != null) {
map.put(c, val+1);
}
}
int start = -1, end = -1;
int i = 0, j = schars.length-1;
while(i <= j) {
if(start == -1) {
Integer val = map.get(schars[i]);
if(val != null) {
if(val == 1) {
start = i;
} else {
map.put(schars[i], val-1);
}
}
i++;
} else {
Integer val = map.get(schars[j]);
if(val != null) {
if(val == 1) {
end = j;
break;
}
map.put(schars[j], val-1);
}
j--;
}
}
if(start == -1 || end == -1) return null;
String ret1 = new String(schars, start, end-start+1);
for(char c : tchars) {
map.put(c, 0);
}
for(char c : schars) {
Integer val = map.get(c);
if(val != null) {
map.put(c, val+1);
}
}
start = -1; end = -1;
i = 0; j = schars.length-1;
while(i <= j) {
if(end == -1) {
Integer val = map.get(schars[j]);
if(val != null) {
if(val == 1) {
end = j;
} else {
map.put(schars[j], val-1);
}
}
j--;
} else {
Integer val = map.get(schars[i]);
if(val != null) {
if(val == 1) {
start = i;
break;
}
map.put(schars[i], val-1);
}
i++;
}
}
String ret2 = new String(schars, start, end-start+1);
return ret1.length() < ret2.length() ? ret1 : ret2;
}

public static void main(String[] args) {
String T = "abc"; // ob
System.out.println("S=" + S);
System.out.println("T=" + T);
System.out.println("Ans=" + findMinimalSubstring(S, T));
}

}

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

O(N) solution where N is the length of the string to search in and considering alphabet size is constant (for this question it seems limited to english letters).

In 2 passes, first starts from end of input and calculates smallest index p to which all characters from search string are found and puts those into array.

Second pass on the created array calculates shortest subarray that contains all characters from string to be searched.

public class MinSubstringContains {
public static String getSubArray(String input, String locate) {
if (input == null || input.isEmpty() || locate == null || locate.isEmpty()) {
return null;
}
int len = input.length();

LastFoundTracker lastFoundTracker = new LastFoundTracker(locate);
int[] closestFound = new int[len];

for(int i = input.length()-1; i>=0; i--) {
closestFound[i] = lastFoundTracker.updateIdx(input.charAt(i), i);
}

int subArrSize = 0;
int subArrStart = 0;
for (int i = 0; i<closestFound.length; i++) {
if (closestFound[i] == Integer.MAX_VALUE) {
break;
}
if (subArrSize == 0 || subArrSize > closestFound[i] - i +1) {
subArrSize = closestFound[i] - i + 1;
subArrStart = i;
}
}

StringBuilder strB = new StringBuilder();
for (int j = 0;j < subArrSize; j++) {
strB.append(input.charAt(subArrStart+j));
}

return strB.toString();
}

public static class LastFoundTracker {
Map<Character, Integer> lastFoundMap = new HashMap<>();
int lastFound = Integer.MAX_VALUE;
public LastFoundTracker(String searchStr) {
for (char c : searchStr.toCharArray()) {
lastFoundMap.put(c, Integer.MAX_VALUE);
}

}
public int updateIdx(char c, int i) {
if (! lastFoundMap.containsKey(c)) {
return lastFound;
}
lastFoundMap.put(c, i);
//find new farthest location that where all chars from search string are found
int max = -1;
for (Integer idx : lastFoundMap.values()) {
if (idx == Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (idx > max) {
max = idx;
}
}
lastFound = max;
return lastFound;
}
}
}

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

/*
* Given arbitrary string `S` and `T`, a string of unique elements, finds the min
* substring of S containing all of T. T needs to be unique for this to work
*/
function minConsecutiveSubstring( arbString, uniqueElements ){
var uniqueCharArray = uniqueElements.split( '' ),
arbStringArr = arbString.split(''),
subs = [],
met = [];
for( var i = 0; i < arbStringArr.length; i++ ){
var item = arbStringArr[i];
if( uniqueCharArray.indexOf( item ) > -1 ){
subs.push({match: [], sub: []});
for( var x in subs ){
if( subs[ x ].match.indexOf( item ) === -1 ){
subs[ x ].match.push( item );
if( subs[ x ].match.length === uniqueCharArray.length ){
met.push( x );
}
}
}
}
// append strings onto substrings generated
for( var x in subs ){
subs[x].sub.push( item );
}
}
return subs[ met.length - 1 ].sub.join( "" );
}

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

js solution for kicks

function minConsecutiveSubstring( arbString, uniqueElements ){
var uniqueCharArray = uniqueElements.split( '' ),
arbStringArr = arbString.split(''),
subs = [],
met = [];
for( var i = 0; i < arbStringArr.length; i++ ){
var item = arbStringArr[i];
if( uniqueCharArray.indexOf( item ) > -1 ){
subs.push({match: [], sub: []});
for( var x in subs ){
if( subs[ x ].match.indexOf( item ) === -1 ){
subs[ x ].match.push( item );
if( subs[ x ].match.length === uniqueCharArray.length ){
met.push( x );
}
}
}
}
// append strings onto substrings generated
for( var x in subs ){
subs[x].sub.push( item );
}
}
return subs[ met.length - 1 ].sub.join( "" );
}

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

Probably the worst possible method but ..
String T = "abc";
int flag = 1;
int min = S.length();
String minstr = "";
for (i = T.length() ; i <= S.length() ;i++)
{
for ( j = 0 ; j <= S.length()-i;j++)
{ flag =1;
String sub = S.substring(j, j+i);
for (int k = 0; k< T.length();k++)
{
if(sub.contains(Character.toString(T.charAt(k))))
flag = 0;
else
{
flag =1;
break;
}

}

if(flag ==0){
if( min > sub.length())
{min = sub.length(); minstr = sub;}
}
}
}
System.out.println("Min substring"+minstr);
}

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

String T = "abc";
int flag = 1;
int min = S.length();
String minstr = "";
for (i = T.length() ; i <= S.length() ;i++)
{
for ( j = 0 ; j <= S.length()-i;j++)
{   flag =1;
String sub = S.substring(j, j+i);
for (int k = 0; k< T.length();k++)
{
if(sub.contains(Character.toString(T.charAt(k))))
flag = 0;
else
{
flag =1;
break;
}

}

if(flag ==0){
if( min > sub.length())
{min = sub.length(); minstr = sub;}
}
}
}
System.out.println("Min substring"+minstr);

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

def solution(a, b):

current_best = None

for i in range(len(a) + 1):
for j in range(len(a) + 1):
if len(set(b) - set(a[i:j])) == 0:
if not current_best or len(current_best) > len(a[i:j]):
current_best = a[i:j]

return current_best

Cut trivial checks:

def solution(a, b):

current_best = None

for i in range(len(a) + 1):
for j in range(len(a) + 1):
if j - i < len(set(b)): continue
if current_best and j - i > len(current_best): continue
if len(set(b) - set(a[i:j])) == 0:
if not current_best or len(current_best) > len(a[i:j]):
current_best = a[i:j]
break

return current_best

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

def find_min_substring(string, target):
target_size = len(target)
string_size = len(string)

for w in range(target_size, string_size):

for i in range(0, string_size - w + 1):
sliced = string[i:i+w]
sliced_set = set()
if set(target).issubset(set(sliced)):
return sliced
else:
return None

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

def find_min_substring(string, target):
target_size = len(target)
string_size = len(string)

for w in range(target_size, string_size):
for i in range(0, string_size - w + 1):
sliced = string[i:i+w]
if set(target).issubset(set(sliced)):
return sliced
else:
return None

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

<?php

\$t = 'abc';

echo findMinSubstring(\$s, \$t);

/**
* @param string \$randomString
* @param string \$uniqueString
*
* @return string
*/
function findMinSubstring(\$randomString, \$uniqueString)
{
\$minSubstring = \$randomString;

while (strlen(\$randomString) > 0)
{
try {
\$result = findSubstring(\$randomString, \$uniqueString);

if (strlen(\$minSubstring) > current(\$result)) {
\$minSubstring = current(\$result);
}

\$randomString = substr(\$randomString, key(\$result) + 1);
}
catch (\Exception \$e) {
break;
}
}

return \$minSubstring;
}

/**
* @param string \$randomString
* @param string \$uniqueString
*
* @return array
*/
function findSubstring(\$randomString, \$uniqueString)
{
\$result = [];

foreach (str_split(\$uniqueString) as \$letter) {
\$result[\$letter] = strpos(\$randomString, \$letter);

if (false === \$result[\$letter]) {
throw new \Exception("No result");
}
}

asort(\$result);

\$firstLetterPos = current(\$result);
\$lastLetterPos = end(\$result);

\$substring = substr(\$randomString, \$firstLetterPos, \$lastLetterPos - \$firstLetterPos + 1);

return [\$firstLetterPos => \$substring];
}

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

I'm sorry, I added it twice

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

<?php

\$t = 'abc';

echo findMinSubstring(\$s, \$t);

/**
* @param string \$randomString
* @param string \$uniqueString
*
* @return string
*/
function findMinSubstring(\$randomString, \$uniqueString)
{
\$minSubstring = \$randomString;

while (strlen(\$randomString) > 0)
{
try {
\$result = findSubstring(\$randomString, \$uniqueString);

if (strlen(\$minSubstring) > strlen(current(\$result))) {
\$minSubstring = current(\$result);
}

\$randomString = substr(\$randomString, key(\$result) + 1);
}
catch (\Exception \$e) {
break;
}
}

return \$minSubstring;
}

/**
* @param string \$randomString
* @param string \$uniqueString
*
* @return array
*/
function findSubstring(\$randomString, \$uniqueString)
{
\$result = [];

foreach (str_split(\$uniqueString) as \$letter) {
\$result[\$letter] = strpos(\$randomString, \$letter);

if (false === \$result[\$letter]) {
throw new \Exception("No result");
}
}

asort(\$result);

\$firstLetterPos = current(\$result);
\$lastLetterPos = end(\$result);

\$substring = substr(\$randomString, \$firstLetterPos, \$lastLetterPos - \$firstLetterPos + 1);

return [\$firstLetterPos => \$substring];
}

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

how this is linear in time?

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

@zahidbuet106 I'm afraid it might be even O (n^2) in the worst-case scenario, but it strongly depends on the input data (e.g. when for S = "aaaaabc", we'll be adding more "a" at the beginning). In optimistic scenario it should be O(n).

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

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

string findBest(const string & s, const string & t) {

string best_str("");
int max = INT_MIN; //Maximum span of sliding window
priority_queue<int, vector<int>, greater<int>> min_heap;
//minimum of sliding window maintained in the top

//Establish baseline sliding window
for (int i = 0; i < t.length(); ++i){
for (int j = 0; j < s.length(); ++j) {
if (s[j] == t[i]) {
min_heap.push(j);
if (j > max) max = j;
break;
}
}
}

if (min_heap.size() != t.length()) return best_str;

int index = min_heap.top();
char elem = s[index];
int best_dist = max - index + 1;
best_str = s.substr(index, best_dist);

//Keep looking for elem, lowest index character
while (true) {

index++;

if (index == s.length()) break;

if (s[index] == elem) {

min_heap.pop();
//Push the new position of elem
min_heap.push(index);

if (index > max) max = index;

//New element to find
index = min_heap.top();
elem = s[index];

//Update best results found so far
if (max - min_heap.top() < best_dist){
best_dist = max - index + 1;
best_str  = s.substr(index, best_dist);
}

}

}

return best_str;

}

int main() {

}

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

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

string findBest(const string & s, const string & t) {

string best_str("");
int max = INT_MIN; //Maximum span of sliding window
priority_queue<int, vector<int>, greater<int>> min_heap;
//minimum of sliding window maintained in the top

//Establish baseline sliding window
for (int i = 0; i < t.length(); ++i){
for (int j = 0; j < s.length(); ++j) {
if (s[j] == t[i]) {
min_heap.push(j);
if (j > max) max = j;
break;
}
}
}

if (min_heap.size() != t.length()) return best_str;

int index = min_heap.top();
char elem = s[index];
int best_dist = max - index + 1;
best_str = s.substr(index, best_dist);

//Keep looking for elem, lowest index character
while (true) {

index++;

if (index == s.length()) break;

if (s[index] == elem) {

min_heap.pop();
//Push the new position of elem
min_heap.push(index);

if (index > max) max = index;

//New element to find
index = min_heap.top();
elem = s[index];

//Update best results found so far
if (max - min_heap.top() < best_dist){
best_dist = max - index + 1;
best_str  = s.substr(index, best_dist);
}

}

}

return best_str;

}

int main() {

}

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

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

string findBest(const string & s, const string & t) {

string best_str("");
int max = INT_MIN; //Maximum span of sliding window
priority_queue<int, vector<int>, greater<int>> min_heap;
//minimum of sliding window maintained in the top

//Establish baseline sliding window
for (int i = 0; i < t.length(); ++i){
for (int j = 0; j < s.length(); ++j) {
if (s[j] == t[i]) {
min_heap.push(j);
if (j > max) max = j;
break;
}
}
}

if (min_heap.size() != t.length()) return best_str;

int index = min_heap.top();
char elem = s[index];
int best_dist = max - index + 1;
best_str = s.substr(index, best_dist);

//Keep looking for elem, lowest index character
while (true) {

index++;

if (index == s.length()) break;

if (s[index] == elem) {

min_heap.pop();
//Push the new position of elem
min_heap.push(index);

if (index > max) max = index;

//New element to find
index = min_heap.top();
elem = s[index];

//Update best results found so far
if (max - min_heap.top() < best_dist){
best_dist = max - index + 1;
best_str = s.substr(index, best_dist);
}

}

}

return best_str;

}

int main() {

}

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

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

string findBest(const string & s, const string & t) {

string best_str("");
int max = INT_MIN; //Maximum span of sliding window
priority_queue<int, vector<int>, greater<int>> min_heap;
//minimum of sliding window maintained in the top

//Establish baseline sliding window
for (int i = 0; i < t.length(); ++i){
for (int j = 0; j < s.length(); ++j) {
if (s[j] == t[i]) {
min_heap.push(j);
if (j > max) max = j;
break;
}
}
}

if (min_heap.size() != t.length()) return best_str;

int index = min_heap.top();
char elem = s[index];
int best_dist = max - index + 1;
best_str = s.substr(index, best_dist);

//Keep looking for elem, lowest index character
while (true) {

index++;

if (index == s.length()) break;

if (s[index] == elem) {

min_heap.pop();
//Push the new position of elem
min_heap.push(index);

if (index > max) max = index;

//New element to find
index = min_heap.top();
elem = s[index];

//Update best results found so far
if (max - min_heap.top() < best_dist){
best_dist = max - index + 1;
best_str  = s.substr(index, best_dist);
}

}

}

return best_str;

}

int main() {

}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[30],in[30],a[1];
int i,j,n,flag=1,m,c,k,cc,u,q,x;
printf("enter the domain string: ");
gets(in);
n=strlen(in);
printf("\nenter the substring(substring characters should not be repeated): ");
gets(s);
m=strlen(s);
for(i=0;i<m;i++){
if(i==0)
{q=1;
a[0]=s[i];}
else if(a[0]!=s[i])
q++;}
if(q<m){
printf(" repeated characters");
flag=0;
x=1;}
if(x!=1){
c=m;
for(u=c;u<=n;u++){
cc=m;
for(i=0;i<=n-u;i++){
for(k=0;k<m;k++){
for(j=i;j<u+i;j++){
if(in[j]==s[k]){
cc--;
break;

if(cc==0){
printf("\nlowest set of consecutive string: ");
for(k=i;k<=j;k++)
printf("%c",in[k]);
flag=0;
break;}
cc=m;}
if(flag==0)
break;}}
if(flag==1)
printf("\nsome characters are missing !!");
getch();}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[30],in[30],a[1];
int i,j,n,flag=1,m,c,k,cc,u,q,x;
printf("enter the domain string: ");
gets(in);
n=strlen(in);
printf("\nenter the substring(substring characters should not be repeated): ");
gets(s);
m=strlen(s);
for(i=0;i<m;i++){
if(i==0)
{q=1;
a[0]=s[i];}
else if(a[0]!=s[i])
q++;}
if(q<m){
printf(" repeated characters");
flag=0;
x=1;}
if(x!=1){
c=m;
for(u=c;u<=n;u++){
cc=m;
for(i=0;i<=n-u;i++){
for(k=0;k<m;k++){
for(j=i;j<u+i;j++){
if(in[j]==s[k]){
cc--;
break;

if(cc==0){
printf("\nlowest set of consecutive string: ");
for(k=i;k<=j;k++)
printf("%c",in[k]);
flag=0;
break;}
cc=m;}
if(flag==0)
break;}}
if(flag==1)
printf("\nsome characters are missing !!");
getch();}

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

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[30],in[30],a[1];
int i,j,n,flag=1,m,c,k,cc,u,q,x;
printf("enter the domain string: ");
gets(in);
n=strlen(in);
printf("\nenter the substring(substring characters should not be repeated): ");
gets(s);
m=strlen(s);
for(i=0;i<m;i++){
if(i==0)
{q=1;
a[0]=s[i];}
else if(a[0]!=s[i])
q++;}
if(q<m){
printf(" repeated characters");
flag=0;
x=1;}
if(x!=1){
c=m;
for(u=c;u<=n;u++){
cc=m;
for(i=0;i<=n-u;i++){
for(k=0;k<m;k++){
for(j=i;j<u+i;j++){
if(in[j]==s[k]){
cc--;
break;}}}
if(cc==0){
printf("\nlowest set of consecutive string: ");
for(k=i;k<=j;k++)
printf("%c",in[k]);
flag=0;
break;}
cc=m;}
if(flag==0)
break;}}
if(flag==1)
printf("\nsome characters are missing !!");
getch();}

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

<?php
\$sub = 'abc';

function splitString(\$string, \$length) {
\$return = [];
for(\$i=0; \$i<=strlen(\$string)-\$length; \$i++) {
\$return[] = substr(\$string, \$i, \$length);
}
return \$return;
}

function findMatchedString(\$string, \$sub) {
\$matchedString = '';
\$min = strlen(\$sub);
\$subArr = str_split(\$sub);
\$i = \$min;

while(1) {
\$break = false;
\$arr = splitString(\$string, \$i);
foreach (\$arr as \$val1) {
\$count = 0;
foreach (\$subArr as \$val2) {
\$pattern = '/'.\$val2.'/';
if(preg_match(\$pattern, \$val1)) {
\$count++;
}
}
if(\$count == \$min) {
\$matchedString = \$val1;
\$break = true;
break;
}
}
if(\$break) {
break;
}
\$i++;
}
return \$matchedString;
}

echo findMatchedString(\$string, \$sub);

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

std::string min_substring(std::string S, std::string T) {

int map[26];
for (int i = 0; i < 26; i++) {
map[i] = -1;
}

for (int i = 0; i < T.size(); i++) {
map[T[i]-'a'] = 0;
}

int counter = 0;
int back = 0;
int res_back = 0, res_front = S.size()+1;
for (int front = 0; front < S.size(); front++) {
if (map[S[front]-'a'] != -1) {
if (0 == map[S[front]-'a'])
counter ++;
map[S[front]-'a']++;
if (counter == T.size()){
// we have seen all the characters in map
while (map[S[back]-'a'] == -1 || map[S[back]-'a'] > 1) {
if (map[S[back]-'a'] > 1) {
map[S[back]-'a'] --;
}
back ++;
}

if (front - back < res_front - res_back){
res_front = front;
res_back = back;
}
}
}
}

return S.substr(res_back, res_front+1);
}

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

simple python solution

def get_length(positions):
keys = positions.keys()
max_ = min_ = positions[keys[0]]
for k in keys:
max_ = max(max_, positions[k])
min_ = min(min_, positions[k])

if min_ == -1:
return -1, min_

return (max_ - min_, min_)

def mix_sub(string, template):
freq = {}
for t in template:
freq[t] = -1

start = -1
l = len(string)

for i in xrange(len(string)):
s = string[i]
if s in freq:
freq[s] = i
(length, min) = get_length(freq)
if 0 < length < l:
l = length
start = min

return string[start: start +l + 1]

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

simple python solution

def get_lenght(positions):
keys = positions.keys()
max_ = min_ = positions[keys[0]]
for k in keys:
max_ = max(max_, positions[k])
min_ = min(min_, positions[k])

if min_ == -1:
return -1, min_

return (max_ - min_, min_)

def min_sub(string, template):
freq = {}
for t in template:
freq[t] = -1

start = -1
l = len(string)

for i in xrange(len(string)):
s = string[i]
if s in freq:
freq[s] = i
(length, min) = get_lenght(freq)
if 0 < length < l:
l = length
start = min

return string[start: start +l + 1]

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

public static bool ContainsEx(string s1, string s2)
{
//s1 contains s2
return String.Concat(s1.OrderBy(c => c).Distinct()).Contains(String.Concat(s2.OrderBy(c => c)));
}
public static string MinConsecutiveSubstring(string s, string t)
{
Queue<int> matches = new Queue<int>();
string matched = "";
int bestStartWindow = -1;
int startWindow = -1;
int length = 0;
int minLength = Int32.MaxValue;
for(int i =0; i < s.Length; i++)
{
if (t.Contains(s[i]))
{
matched = matched + s[i];
matches.Enqueue(i);
}

while (ContainsEx(matched,t))
{
// end window reached
startWindow = matches.Dequeue();
length = i - startWindow+1;
if (length < minLength)
{
minLength = length;
bestStartWindow = startWindow;
// store start and end later on
}

// remove first character from matched and check if still matched
matched = matched.Substring(1);

}

}

if (bestStartWindow > -1)
return s.Substring(bestStartWindow, minLength);
else
return string.Empty;
}

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

public static bool ContainsEx(string s1, string s2)
{
//s1 contains s2
return String.Concat(s1.OrderBy(c => c).Distinct()).Contains(String.Concat(s2.OrderBy(c => c)));
}
public static string MinConsecutiveSubstring(string s, string t)
{
Queue<int> matches = new Queue<int>();
string matched = "";
int bestStartWindow = -1;
int startWindow = -1;
int length = 0;
int minLength = Int32.MaxValue;
for(int i =0; i < s.Length; i++)
{
if (t.Contains(s[i]))
{
matched = matched + s[i];
matches.Enqueue(i);
}

while (ContainsEx(matched,t))
{
// end window reached
startWindow = matches.Dequeue();
length = i - startWindow+1;
if (length < minLength)
{
minLength = length;
bestStartWindow = startWindow;
// store start and end later on
}

// remove first character from matched and check if still matched
matched = matched.Substring(1);

}

}

if (bestStartWindow > -1)
return s.Substring(bestStartWindow, minLength);
else
return string.Empty;
}

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

bool findSmallestSubStr(const string S, const string T, int& start, int& end)
{
start = end = -1;
bool found = false;
unordered_set<char> TSet;
for(int i = 0; i < T.size(); ++i) {
TSet.insert(T.at(i));
}

queue<pair<int, char>> Q;
map<char, int> m;

int = 0;
size_t minLen = S.size() + 1;
for(int j = 0; j < S.size(); ++j) {
const char& c = S.at(j);
if (TSet.find(c) == TSet.end()) {
continue;
}

Q.push_back(pair<int,char>(j, c));
M[c]++;
if (M.size() == T.size()) {
found = true;
if (j - i - 1 < minLen) {
minLen = j - i - 1;
start = i;
end = j;
}

pair<int,char>& p = Q.front();
Q.pop();
if (--M[p.second] == 0) {
M.erase(p.second);
}
}
}
return false;
}

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

JavaScript Solution. I'm not exactly sure what the time complexity of this is.

I think in the best case it is O(n), and in the worst case it is O(n log n).

function minSubstring(source, elements) {
var sets = [];
var chars = {};
var history = {};
elements.split('').map(function(value) {
chars[value] = undefined;
});

source.split('').map(function(value, index) {
if (chars.hasOwnProperty(value)) {
history[value] = index;

if (Object.keys(history).length === elements.length) {
var range = Object.values(history);
range.sort(function(a,b){
return a-b
});

sets.push({
start: range[0],
end: range[range.length -1]
});
}
}
});

var range = Object.values(sets)
range.sort(function(a,b){
return (b.end - b.start) -(a.end - a.start);
});
var smallestRange = range.pop();
return source.slice(smallestRange.start, smallestRange.end +1);
}

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

static String findSubs(String s, String t) {

int[] arr = new int[t.length()];
String best = s, copyofS = s;

while (arr[0] >= 0) {

for (int i = 0; i < t.length(); i++) {
arr[i] = copyofS.indexOf(String.valueOf(t.charAt(i)));
}

Arrays.sort(arr);

if (best.length() > (arr[arr.length - 1] - arr[0] + 1)) {
best = copyofS.substring(arr[0], arr[arr.length - 1] + 1);
}

copyofS = copyofS.substring(arr[0] + 1);
}
return best;
}

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

static String findSubs(String s, String t) {

int[] arr = new int[t.length()];
String best = s, copyofS = s;

while (arr[0] >= 0) {

for (int i = 0; i < t.length(); i++) {
arr[i] = copyofS.indexOf(String.valueOf(t.charAt(i)));
}

Arrays.sort(arr);

if (best.length() > (arr[arr.length - 1] - arr[0] + 1)) {
best = copyofS.substring(arr[0], arr[arr.length - 1] + 1);
}

copyofS = copyofS.substring(arr[0] + 1);
}
return best;

}

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

Python style:

def findMinConsecutiveSet(findme, arr):
if findme is None or len(findme) == 0 or arr is None or len(arr) == 0 or len(findme) > len(arr):
return ""
positions = [-1]*len(findme)
found = 0
mini , maxi = 0 ,0
foundlen = len(findme) + 1
winninglocation = ""
for i in range(len(arr)):
if arr[i] in findme:
found += 1
positions[findme.index(arr[i])] = i
if found >= len(findme):
mini = min(positions)
maxi = max(positions)
if foundlen > maxi - mini:
foundlen = maxi - mini
winninglocation = "max:"+str(maxi)+" min:"+str(mini)

if found >= len(findme):
print(winninglocation)
else:
"didn't find"

T = ["A","B","C"]
S = ["A", "D", "A", "B", "D", "A", "B", "D", "C", "A" ,"B"]
findMinConsecutiveSet(T,S)

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

Suffix tree is the answer to this question.

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.