Facebook Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
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])
This is insanely complicated for a solution to this problem. I'm also pretty sure creating all the permutations is not very efficient.
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
}
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*S ="adobecodebanc";
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;
}
@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".
#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 s="adobecodebanc";
string t="abc";
findIt(s,t);
cout<<endl;
getchar();
return 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;
}
}
#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 s="adobecodebanc";
string t="abc";
findIt(s,t);
cout<<endl;
getchar();
return 0;
}
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;
}
print_r(shortest_has_all("adobecodebanc", ["a","b","c"]));
#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());
}
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
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 givenStr = "adobecodebanckkjldfgkldfgasdfasbckalsdfjalsdf";
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:
Given String: adobecodebanckkjldfgkldfgasdfasbckalsdfjalsdf
To find set: abc
Found at: 9. Length: 4. SubString: banc
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())
{
target.add(c);
}
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));
}
q.add(i);
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]));
}
}
import java.util.HashSet;
public class Longestmatch {
public static void main(String[] args) {
System.out.println("ans="+ match("adobecodebanc","abc"));
}
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));
map.add(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;
}
}
import java.util.HashSet;
public class Longestmatch {
public static void main(String[] args) {
System.out.println("ans="+ match("adobecodebanc","abc"));
}
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));
map.add(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;
}
}
import java.util.HashSet;
public class Longestmatch {
public static void main(String[] args) {
System.out.println("ans="+ match("adobecodebanc","abc"));
}
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));
map.add(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;
}
}
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));
}
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;
}
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;
}
O(n) solution
public static void main(String[] args) {
String S = "adobecodebanc";
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);
}
#include<string>
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector <int> buf;
string s="adobecodebanc";
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;
}
string s = "adobecabbacodebanc";
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;
}
}
string s = "adobecabbacodebanc";
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;
}
}
string s = "adobecabbacodebanc";
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;
}
}
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);
}
- 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 S = "adobecodebanc";
String T = "abc"; // ob
System.out.println("S=" + S);
System.out.println("T=" + T);
System.out.println("Ans=" + findMinimalSubstring(S, T));
}
}
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;
}
}
}
/*
* 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( "" );
}
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( "" );
}
Probably the worst possible method but ..
{String S = "adobecodebanc";
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);
}
String S = "adobecodebanc";
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);
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
<?php
$s = 'adobecodebanc';
$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];
}
<?php
$s = 'adobecodebanc';
$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];
}
#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() {
cout<<findBest("adobecodebanc", "abc");
}
#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() {
cout<<findBest("adobecodebanc", "abc");
}
#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() {
cout<<findBest("adobecodebanc", "abc");
}
#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() {
cout<<findBest("adobecodebanc", "abc");
}
#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();}
#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();}
#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();}
<?php
$string = 'adobecodebanc';
$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);
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);
}
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]
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]
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;
}
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;
}
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;
}
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);
}
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;
}
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;
}
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)
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.
- zahidbuet106 December 11, 2015