Facebook Interview Question for Software Developers


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

- zahidbuet106 December 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wonderful and elegant solution. Thumbs up!

- dhs.du.08 December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't it looks like Kadane's algorithm?

- dhs.du.08 December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zahidbuet106 December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very elegant and indeed a great solution. :D

- pujun@cs.stanford.edu February 18, 2016 | Flag
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])

- Saghar H November 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- foobar November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ScottyMitch88 November 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

quite complicated. Could you please explain?

- dhs.du.08 December 11, 2015 | Flag
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 
}

- R@M3$H.N November 05, 2015 | Flag Reply
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?

- koosha.nejad November 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 November 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- venkatesh.duggirala November 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how is this code run in O(n)?

- zahidbuet106 December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dhs.du.08 December 11, 2015 | Flag
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 s="adobecodebanc";
	string t="abc";
	findIt(s,t);
	cout<<endl;
	getchar();
	return 0;
}

- Anonymous November 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 06, 2015 | Flag
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 s="adobecodebanc";
	string t="abc";
	findIt(s,t);
	cout<<endl;
	getchar();
	return 0;
}

- Anonymous November 05, 2015 | Flag Reply
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;
}

print_r(shortest_has_all("adobecodebanc", ["a","b","c"]));

- ben November 05, 2015 | Flag Reply
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());
}

- Rahul Vaidya November 06, 2015 | Flag Reply
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

- liujingchu November 06, 2015 | Flag Reply
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 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

- MongoLikeCode November 06, 2015 | Flag Reply
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())
    {
      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]));
  }
}

- Anonymous November 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

R

s <- 'adobecodebanc' 
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
}

- Mr.JoshuaGordon November 07, 2015 | Flag Reply
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) {
		
		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;
	}
}

- Anuradha November 08, 2015 | Flag Reply
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) {
		
		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;
	}
}

- sainianu08 November 08, 2015 | Flag Reply
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) {
		
		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;
	}
}

- sainianu08 November 08, 2015 | Flag Reply
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));
    }

- CPluspluser November 08, 2015 | Flag Reply
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

- allen.lipeng47 November 09, 2015 | Flag Reply
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;
        }

- jack.shih November 09, 2015 | Flag Reply
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;
        }

- jak.shih November 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ikoryf November 09, 2015 | Flag Reply
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 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;
}

- Anonymous November 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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#... Maybe O(m*n) but it was fun writing it :) November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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#... Maybe O(m*n) but it was fun writing it :) November 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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#... Maybe O(m*n) but it was fun writing it :) November 10, 2015 | Flag Reply
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);
}

- Newbie November 12, 2015 | Flag Reply
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 S = "adobecodebanc";
        String T = "abc"; // ob
        System.out.println("S=" + S);
        System.out.println("T=" + T);
        System.out.println("Ans=" + findMinimalSubstring(S, T));
    }
    
}

- HG November 15, 2015 | Flag Reply
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;
		}
	}
}

- blckembr November 16, 2015 | Flag Reply
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( "" );
}

- JS solution just for kicks November 27, 2015 | Flag Reply
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( "" );
}

- smitchell November 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kj1004 November 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- kj November 29, 2015 | Flag Reply
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

- alvarovmz November 29, 2015 | Flag Reply
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

- Anonymous December 01, 2015 | Flag Reply
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

- hiroshi December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm sorry, I added it twice

- abobola December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- abobola December 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how this is linear in time?

- zahidbuet106 December 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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).

- abobola December 30, 2015 | Flag
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() {
	
	cout<<findBest("adobecodebanc", "abc");

}

- sud December 15, 2015 | Flag Reply
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() {
	
	cout<<findBest("adobecodebanc", "abc");

}

- sud December 15, 2015 | Flag Reply
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() {

cout<<findBest("adobecodebanc", "abc");

}

- sud December 15, 2015 | Flag Reply
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() {
	
	cout<<findBest("adobecodebanc", "abc");

}

- sud December 15, 2015 | Flag Reply
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();}

- c solution, with user input December 23, 2015 | Flag Reply
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();}

- c solution, with user input December 23, 2015 | Flag Reply
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();}

- c solution, with user input December 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?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);

- Sandy December 25, 2015 | Flag Reply
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);
}

- gigilibala February 15, 2016 | Flag Reply
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]

- vladimir.ovsyannikov March 27, 2016 | Flag Reply
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]

- vladimir.ovsyannikov March 27, 2016 | Flag Reply
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;
        }

- saisatish May 22, 2016 | Flag Reply
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;
        }

- saisatish May 22, 2016 | Flag Reply
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;
}

- Rohit Jog January 11, 2017 | Flag Reply
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);
}

- nabilgod January 14, 2017 | Flag Reply
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;
	}

- MS October 06, 2017 | Flag Reply
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;

}

- MS October 06, 2017 | Flag Reply
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)

- Ronen September 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Suffix tree is the answer to this question.

- Dishant Shahani February 22, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More