Facebook Interview Question Interns
Country: United States
Interview Type: Phone Interview
@Scott, why "if (c == 1) count++; " ? count++ needs to be increased anyway.. when you find the char in the set..
Is this algo O(n x m), where n is length of string and m is length of set.
One minor improvement can be adding the following condition at the end of the while loop :
if (minLen == set.size()) {
return result
}
For people trying to understand the algorithm: the for loop is basically for walking the string character by character; the while loop enters only when you have a substring (from indices tail to i, inclusive) that's the potential candidate. The second if in there checks if this candidate is shorter than one you had, and saves the substring. When the for finishes you'll have the shortest string that meets the requirement
Very Nice. Took me a while to do similar implementation but I used a queue to keep valid chars instead off keeping the tail position.
I was going to suggest that once you find that the tail in the map is 1 that is when you should be comparing the minLen as that is when you actually find the minimum length of the current subset.
Explanation:
First of all we need to find the smallest substring from 0 to i that contains all necessary elements. It's the first answer, but we may try to improve it (find shorter substring). Let's put tail = 0 and head = i. Then iteratively increase head index and each time we check if we can cut tail: we can do it, if charAt(tail) presented more than one time in substring(tail,head) or it's not presented in set of chars. Each time we cut the tail, check if the length of the new substring is smaller and if it is - remember answer.
private static String getSubstring(String str , HashSet<Character> chars){
int head_ans = -1;
int tail_ans = -1;
int length = Integer.MAX_VALUE;
int head = 0;
HashMap<Character, Integer> charCount = new HashMap<>();
for (int tail = 0; tail < str.length(); tail++){
char currChar = str.charAt(tail);
if (!chars.contains(currChar)){
continue;
}
charCount.put(currChar , charCount.containsKey(currChar) ? charCount.get(currChar) + 1 : 1);
while(true){
char headChar = str.charAt(head);
if (!chars.contains(headChar)){
head++;
continue;
}
int headCharCount = charCount.get(headChar);
if (headCharCount == 1) {
break;
}
head++;
charCount.put(headChar , headCharCount - 1);
}
if (charCount.size() == chars.size() && (tail - head + 1) < length){
tail_ans = tail;
head_ans = head;
length = tail-head+1;
}
}
return (tail_ans != -1) ? str.substring(head_ans , tail_ans+1) : "";
}
Implementation in Python
def valid(M):
for k, v in M.iteritems():
if v == 0:
return False
return True
seq = "abbcbcba"
S = set(['a', 'b', 'c'])
M = dict()
for i in S:
M[i] = 0
i = 0
j = 0
n = len(seq)
length = n+1
while j < n:
if seq[j] in S:
M[seq[j]] += 1
if valid(M) and (j-i+1) < length:
length = j-i+1
while valid(M):
if seq[i] in S:
if M[seq[i]] == 1:
break
M[seq[i]] -= 1
i += 1
if (j-i+1) < length:
print seq[i:j+1]
length = j-i+1
j += 1
print length
In C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;
int main() {
set<char> s;
int j;
string str, str2;
int hash, hash2;
s.insert('a');
s.insert('b');
s.insert('c');
cin>>str;
for(set<char>::iterator i = s.begin(); i!=s.end(); i++){
hash+=(int)(*i);
}
for(int i=0;i<str.length()-s.size()+1;i++){
j=i;
hash2 = 0;
str2.clear();
while(j<(i+3)){
str2.push_back(str[j]);
hash2+=(int)str[j];
j++;
}
if(hash2 == hash){
cout<<str2<<endl;
break;
}
}
return 0;
}
public String getSmallestSuperSubString( Set<Character> characters, String string){
if(string.length()<1 || characters.isEmpty()){
return null;
}
//record all the characters that occur to the left and right of each string index
List<Set<Character>> charactersToTheRight = new ArrayList<>();
List<Set<Character>> charactersToTheLeft= new ArrayList<>();
Set<Character> accumalator = new HashSet<>();
for (int i = 0; i < string.length(); i++) {
Set<Character> left = new HashSet<>();
left.addAll(accumalator);
charactersToTheLeft.add(left);
charactersToTheRight.add(left);
accumalator.add(string.charAt(i));
}
accumalator.clear();
for (int i = string.length()-1; i >= 0; i--) {
Set<Character> right = new HashSet<>();
right.addAll(accumalator);
charactersToTheRight.set(i,right);
accumalator.add(string.charAt(i));
}
//Check that the string does contain them all
if(!charactersToTheLeft.get(string.length()-1).containsAll(characters)){
return null;
}
//move the left index right till characters to the right no longer contain all chars
int leftIndex=0;
while(charactersToTheRight.get(leftIndex).containsAll(characters)){
leftIndex++;
}
//move the right index left till characters to the left no longer contain all chars
int rightIndex=string.length()-1;
while(charactersToTheLeft.get(rightIndex).containsAll(characters)){
rightIndex--;
}
return string.substring(leftIndex,rightIndex+1);
}
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class CoverAllCharacters {
String s;
public CoverAllCharacters(String s){
this.s = s;
}
String computeMinCover(char[] goodChar){
if(s==null){
return null;
}
int k = goodChar.length;
char sc[] = s.toCharArray();
Map<Character, List<Integer>> charLocations = new HashMap<Character, List<Integer>>();
for(char c : goodChar){
charLocations.put(c, new LinkedList<Integer>());
}
for(int i = 0; i < sc.length; i++){
char c = sc[i];
charLocations.get(c).add(i);
}
Map<Character, Integer> earliestLocationInSubstring = new HashMap<Character, Integer>();
/*for(char c : goodChar){
earliestLocationInSubstring.put(c, -1);
}*/
int start = 0;
int bestCoverLength = Integer.MAX_VALUE, bestCoverStart=-1;
for(int i = 0; i < sc.length; i++){
char c = sc[i];
if(!earliestLocationInSubstring.containsKey(c)){
earliestLocationInSubstring.put(c, i);
}
if(earliestLocationInSubstring.size() == k){
boolean done = false;
int nextLocationOfChar;
do {
int coverLength = i+1-start;
if(coverLength < bestCoverLength){
bestCoverStart=start;
bestCoverLength=coverLength;
}
char startChar = sc[start];
charLocations.get(startChar).remove(0);
nextLocationOfChar = (charLocations.get(startChar).size() > 0) ? charLocations.get(startChar).get(0) : -1;
if(nextLocationOfChar == -1){
break;
}
start=start+1;
done = (nextLocationOfChar > i);
if(done) {
earliestLocationInSubstring.remove(startChar);
}
} while(!done);
if(nextLocationOfChar == -1){
break;
}
}
}
String res = null;
if(bestCoverStart >= 0){
res = s.substring(bestCoverStart, bestCoverStart+bestCoverLength);
}
return res;
}
public static void main(String[] args){
String[] testcases = {"abbcbcba" , "abbcbcbba"};
char[] alphabet = { 'a' , 'b' , 'c' };
for(String s : testcases){
CoverAllCharacters wrapper = new CoverAllCharacters(s);
String cover = wrapper.computeMinCover(alphabet);
System.out.println(s + "\t" + cover);
}
}
}
The Following fully working code. Time Complexity - O(n*lg n) .
#include<string>
#include<set>
#include<iostream>
#include<map>
using namespace std;
string minLength(const set<char> &s, const string word)
{
int low = s.size(), high = word.size()-1, mid;
map<char,int> counting_map;
int count;
while(low < high)
{
mid = low + (high-low)/2;
bool flag = false;
count = 0;
counting_map.clear();
/*code to check whether we can have a string of len mid
* which contains all characters of the set.
*/
for(int i=0; i<mid; i++)
{
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
}
if(count == s.size())
flag = true;
else
{
for(int i= mid; i<word.size(); i++)
{
counting_map[word[i-mid]]--;
if(counting_map[word[i-mid]] == 0)
count--;
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
if(count == s.size())
{
flag = true;
break;
}
}
}
if(flag)
{
high = mid;
}
else
{
low = mid+1;
}
}
/*low is the length of the substring with the given properties*/
count = 0;
counting_map.clear();
cout << "min lengthh is - " << low <<endl;
for(int i=0; i<low; i++)
{
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
}
cout <<"count-1: " <<count ;
if(count == s.size())
return word.substr(0, low);
for(int i= low; i<word.size(); i++)
{
counting_map[word[i-low]]--;
if(counting_map[word[i-low]] == 0)
count--;
cout <<"count-2: " <<count ;
counting_map[word[i]]++;
// To count one char once only.
if(counting_map[word[i]] == 1)
count++;
cout <<"count-3: " <<count ;
if(count == s.size())
return word.substr(i-low+1, low);
}
return "?";
}
int main()
{
set<char> s;
s.insert('a');
s.insert('b');
s.insert('c');
string word = "baacaab";
cout << "min_length_substring.cpp\n";
cout << "\n Substring (Ans) = " << minLength(s,word);
return 0;
}
java script solution : O(n)
//List Datastructure
indList = {
start: null,
end: null,
add: function(ele){
var node = {
next: null,
prev: null,
val: ele
};
if(!this.end){
this.start = this.end = node;
}else{
this.end.next = node;
node.prev = this.end;
this.end = node;
}
return node;
},
remove: function(node){
if(node.prev){
node.prev.next = node.next;
}else if(this.start == node){
this.start = node.next;
}
if(node.next){
node.next.prev = node.prev;
}else if(this.end == node){
this.end = node.prev;
}
}
};
var solution = {
//input start
set: {
a: true,
b: true,
c: true
},
str: 'abbcbcba',
//input end
indexes: indList,
cnt: 0,
map: {},
add: function(ind){
var char = this.str.charAt(ind);
if(!this.set[char]){
return;
}
this.remove(char);
this.cnt++;
this.map[char] = this.indexes.add(ind);
},
remove: function(char){
if(this.map[char]){
this.cnt--;
this.indexes.remove(this.map[char]);
this.map[char] = null;
}
},
solve: function(){
var setLen = Object.keys(this.set).length,
curSolution = {
length: this.str.length + 1,
subStr: ''
},
len;
for(var i = 0, l = this.str.length; i < l; i++){
this.add(i);
if(this.cnt == setLen){
len = this.indexes.end.val - this.indexes.start.val + 1;
if(len < curSolution.length){
curSolution.length = len;
curSolution.subStr = this.str.slice(this.indexes.start.val, this.indexes.end.val + 1);
}
this.remove(this.str.charAt(this.indexes.start.val));
}
}
return curSolution;
}
};
solution.solve();
//List Datastructure
indList = {
start: null,
end: null,
add: function(ele){
var node = {
next: null,
prev: null,
val: ele
};
if(!this.end){
this.start = this.end = node;
}else{
this.end.next = node;
node.prev = this.end;
this.end = node;
}
return node;
},
remove: function(node){
if(node.prev){
node.prev.next = node.next;
}else if(this.start == node){
this.start = node.next;
}
if(node.next){
node.next.prev = node.prev;
}else if(this.end == node){
this.end = node.prev;
}
}
};
var solution = {
//input start
set: {
a: true,
b: true,
c: true
},
str: 'abbcbcba',
//input end
indexes: indList,
cnt: 0,
map: {},
add: function(ind){
var char = this.str.charAt(ind);
if(!this.set[char]){
return;
}
this.remove(char);
this.cnt++;
this.map[char] = this.indexes.add(ind);
},
remove: function(char){
if(this.map[char]){
this.cnt--;
this.indexes.remove(this.map[char]);
this.map[char] = null;
}
},
solve: function(){
var setLen = Object.keys(this.set).length,
curSolution = {
length: this.str.length + 1,
subStr: ''
},
len;
for(var i = 0, l = this.str.length; i < l; i++){
this.add(i);
if(this.cnt == setLen){
len = this.indexes.end.val - this.indexes.start.val + 1;
if(len < curSolution.length){
curSolution.length = len;
curSolution.subStr = this.str.slice(this.indexes.start.val, this.indexes.end.val + 1);
}
this.remove(this.str.charAt(this.indexes.start.val));
}
}
return curSolution;
}
};
solution.solve();
public class StringSearchDemo {
public String getSmallestSubsetOfStringContaingSearchString(String toMatch,
String inputString) {
if (inputString.isEmpty() || toMatch.isEmpty()) {
return null;
}
// List<String> results = new ArrayList<String>(); // optional you can comment this out
String smallestMatch = "";
// String largestMatch = "";
int startPointer = 0, endPointer = 1;
HashMap<Character, Integer> toMatchMap = new HashMap<Character, Integer>();
for (char c : toMatch.toCharArray()) {
if (toMatchMap.containsKey(c)) {
toMatchMap.put(c, (toMatchMap.get(c) + 1));
} else {
toMatchMap.put(c, 1);
}
}
int totalCount = getCountofMatchingString(toMatchMap, toMatch);
for (int i = 0; i < inputString.length();) {
if (!toMatchMap.containsKey(inputString.charAt(i))) {
endPointer++;
i++;
continue;
}
String currentSubString = inputString.substring(startPointer,
endPointer);
if (getCountofMatchingString(toMatchMap, currentSubString) >= totalCount) {
// results.add(currentSubString); // optional you can comment this out
if (smallestMatch.length() > currentSubString.length()) {
smallestMatch = currentSubString;
} else if (smallestMatch.isEmpty()) {
smallestMatch = currentSubString;
}
// if (largestMatch.length() < currentSubString.length()) {
// largestMatch = currentSubString;
// }
startPointer++;
} else {
endPointer++;
i++;
}
}
// System.out.println("all possible combinations = " + results); // optional, you can comment this out
// System.out.println("smallest result = " + smallestMatch);
// System.out.println("largest result = " + largestMatch);
return smallestMatch;
}
public int getCountofMatchingString(HashMap<Character, Integer> toMatchMap,
String toMatch) {
int match = 0;
HashMap<Character, Integer> localMap = new HashMap<Character, Integer>();
for (char c : toMatch.toCharArray()) {
if (toMatchMap.containsKey(c)) {
if (localMap.containsKey(c)) {
if (localMap.get(c) < toMatchMap.get(c)) {
localMap.put(c, (localMap.get(c) + 1));
match++;
}
} else {
localMap.put(c, 1);
match++;
}
}
}
return match;
}
public static void main(String[] args) {
String inputString = "zxaddbddxyy由ccbbwwaay漢字由来";
String matchCriteria = "a由";
System.out.println("input=" + matchCriteria);
System.out.println("matchCriteria=" + inputString);
String result = (new StringSearchDemo())
.getSmallestSubsetOfStringContaingSearchString(matchCriteria, inputString);
System.out.println("smallest possbile match = " + result);
}
}
Hey guys,
Here is my recursive solution, feel free to make comments if you find any issue with it:
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
public class FindSubstring {
public static String findSubstring(char[] val, char[] input)
{
Set<Character> s = new LinkedHashSet<Character>(); // Maintain the insertion order
Set<Character> values = new HashSet<Character>();
for(Character c : val)
values.add(c);
Set<Character> result = findSubstringAux(values, input, 0, s);
return result.toString();
}
private static Set<Character> findSubstringAux(Set<Character> values, char[] input, Integer i, Set<Character> s)
{
char c = input[i];
if(i < input.length)
{
if(i + 1 < input.length){
if(!s.contains(c) && !s.contains(input[i + 1])){
s.add(c);
return findSubstringAux(values, input, ++i, s);
}else{
s.clear();
return findSubstringAux(values, input, i, s);
}
}
}
if(!s.contains(c))
s.add(c);
if(s.size() != values.size())
s.clear();
return s;
}
public static void main(String[] args) {
char[] val = {'a', 'b', 'c'};
char[] input1 = {'a','b','b','c','b','c','b','a'};
char[] input2 = {'a','a','a','a','a','a','b','c'};
char[] input3 = {'a','a','a'};
char[] input4 = {'a','b','c'};
char[] input5 = {'a','b'};
System.out.println(String.format("Values to check = %s", Arrays.toString(val)));
System.out.println(String.format("Input 1 %s - Solution = %s", Arrays.toString(input1), findSubstring(val, input1)));
System.out.println(String.format("Input 2 %s - Solution = %s", Arrays.toString(input2), findSubstring(val, input2)));
System.out.println(String.format("Input 3 %s - Solution = %s", Arrays.toString(input3), findSubstring(val, input3)));
System.out.println(String.format("Input 4 %s - Solution = %s", Arrays.toString(input4), findSubstring(val, input4)));
System.out.println(String.format("Input 5 %s - Solution = %s", Arrays.toString(input5), findSubstring(val, input5)));
}
}
I solved using recursion but I see that an iterative is possible.
void Main()
{
char[] p = new char[]{'a','b','c'};
string a1 = "abbcbcba";
Console.WriteLine(GetMinDistance(a1, p));
}
public static string GetMinDistance(string A, char[] P)
{
Dictionary<char, int> ht = new Dictionary<char, int>();
foreach(char p in P)
{
if(!ht.ContainsKey(p))
{
ht.Add(p, 1);
}
else
{
ht[p]++;
}
}
Tuple<int, int> min = new Tuple<int, int>(0, int.MaxValue);
int minDistance = min.Item2 - min.Item1;
for(int i = 0; i < (A.Length - P.Length + 1); i++)
{
Tuple<int, int> temp = GetMinDistanceHelper(A, ht, i, P.Length);
Console.WriteLine(temp);
// This means the reamining string did not found the set P
if(temp.Item2 == int.MaxValue) break;
int tempDistance = (temp.Item2 - temp.Item1);
if( tempDistance < minDistance)
{
min = temp;
minDistance = tempDistance;
// Means this is the minimum possible set
if(minDistance == P.Length - 1)
break;
}
// Move the i to the first occurence of a char in the set
if(temp.Item1 > i)
{
i = temp.Item1 + 1;
}
}
if(min.Item2 == int.MaxValue) throw new ArgumentException("Array P is not present in string A");
return A.Substring(min.Item1, minDistance);
}
private static Tuple<int, int> GetMinDistanceHelper(
string A,
Dictionary<char, int> ht,
int start,
int remaining)
{
Console.WriteLine(remaining);
Console.WriteLine(ht);
if(remaining == 0)
return new Tuple<int,int>(start, start);
for(int i = start; i < (A.Length - remaining + 1); i++)
{
char c = A[i];
if(ht.ContainsKey(c) && ht[c] > 0)
{
ht[c]--;
Tuple<int, int> temp = GetMinDistanceHelper(A, ht, i + 1, remaining - 1);
ht[c]++;
return new Tuple<int, int>(i, temp.Item2);
}
}
return new Tuple<int,int>(A.Length, int.MaxValue);
}
Solution with Ruby
array = ["a", "b", "c"]
string = "abbcbcba"
string_array = string.split("")
string_length = string_array.length
string_array.each_with_index do |letter, index|
if index +2 <= string_length
substring = [letter, string_array[index+1], string_array[index+2]]
if substring.sort == array
p substring
break
end
end
end
Solution with JS
function smallestSubstring(set, str) {
var hash = {},
j = set.length,
result = [0, str.length],
start = 0;
for (var i = 0; i < set.length; i++) {
hash[set[i]] = 1;
}
str = str.split("");
for (i = 0; i < str.length; i++) {
if (hash.hasOwnProperty(str[i]) === true && --hash[str[i]] === 0) {
if (--j === 0) {
while (hash[str[start]] !== 0) {
hash[str[start]]++;
start++;
}
if ((i - start) < (result[1] - result[0])) {
result = [start, i + 1];
}
for (key in hash) {
if (hash.hasOwnProperty(key) === true) {
hash[key] = 1;
j++;
}
}
start = i + 1;
}
}
}
return str.slice(result[0], result[1]).join("");
}
Actually the above doesn't handle the case "aabbcba", but this should:
function smallestSubstring(set, str) {
var hash = {},
j = set.length,
result = [0, str.length],
start = 0, isFound = false;
for (var i = 0; i < set.length; i++) {
hash[set[i]] = 1;
}
str = str.split("");
for (i = 0; i < str.length; i++) {
if (hash.hasOwnProperty(str[i]) === true && --hash[str[i]] === 0) {
if (--j === 0) {
while (++hash[str[start++]] < 1) {
}
if ((i - start + 2) < (result[1] - result[0])) {
result = [start - 1, i + 1];
isFound = true;
}
j++;
}
}
}
if (isFound === true) {
return str.slice(result[0], result[1]).join("");
}
}
Python
import copy
def foo_bruth_force(Set,String):
positions = {char:[] for char in Set}
for i in range(len(String)):
if String[i] in positions:
positions[String[i]].append(i)
# positions {'a':[0,7],'b':[1,2,4,6],'c':[3,5],'d'....,'e',}
positions = [positions[key] for key in positions]
output = min(helper(positions), key=minmax )
return String[output[0]:output[-1]+1]
# lst is a list of lists
# return a list of numbers
def helper(lst):
lst = copy.deepcopy(lst)
if len(lst)==0: return []
sublst = lst.pop()# sublst [0,7]
right = helper(lst) # a list of lists
output = []
for x in sublst:
if len(lst)!=0:
output += [ [x]+sub for sub in right]
else:
output.append([x])
return output
def minmax(lst):
lst.sort()
return lst[-1]-lst[0]
print foo_bruth_force(['a','b','c'],'abbcbcba')
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println("Hello World");
HashSet<Character> set = new HashSet<Character>();
set.add('a');
set.add('b');
set.add('c');
String s = "abbcbcba";
System.out.println(findMin(s,set));
}
public static String findMin(String s, HashSet<Character> set)
{
int size = set.size();
int len = s.length();
if (size > len)
return null;
else if (set.isEmpty())
return "";
else if(size==len)
{
for(Character c: set)
{
if(s.indexOf(c)==-1)
return null;
}
return s;
}
for(Character c: set)
{
if(s.indexOf(c)==-1)
return null;
}
Boolean hasChar = true;
for(int l = size; l <= len; l++)
{
for (int i = 0; i <= len - size; i++)
{
hasChar = true;
String substr = s.substring(i,i+l);
for(Character c: set)
{
if(substr.indexOf(c)==-1)
{
hasChar = false;
break;
}
}
if(hasChar)
return substr;
}
}
return null;
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.println("Hello World");
HashSet<Character> set = new HashSet<Character>();
set.add('a');
set.add('b');
set.add('c');
String s = "abbcbcba";
System.out.println(findMin(s,set));
}
public static String findMin(String s, HashSet<Character> set)
{
int size = set.size();
int len = s.length();
if (size > len)
return null;
else if (set.isEmpty())
return "";
else if(size==len)
{
for(Character c: set)
{
if(s.indexOf(c)==-1)
return null;
}
return s;
}
for(Character c: set)
{
if(s.indexOf(c)==-1)
return null;
}
Boolean hasChar = true;
for(int l = size; l <= len; l++)
{
for (int i = 0; i <= len - size; i++)
{
hasChar = true;
String substr = s.substring(i,i+l);
for(Character c: set)
{
if(substr.indexOf(c)==-1)
{
hasChar = false;
break;
}
}
if(hasChar)
return substr;
}
}
return null;
}
}
public static void main(String[] args) {
finSmall bin = new finSmall();
Set<Character> s = new HashSet<Character>();
s.add('a');
s.add('b');
s.add('c');
String str = "aabbcba";
String p = bin.smallestCom(s, str, 3);
System.out.println(p);
}
public boolean compare(Set<Character> a,String s) {
Map<Character,Integer> m = new HashMap<Character,Integer>();
int val=0;
for(int i =0;i<s.length();i++) {
if(a.contains(s.charAt(i))) {
if(!m.containsKey(s.charAt(i)))
m.put(s.charAt(i),1 );
else {
val = m.get(s.charAt(i));
m.put(s.charAt(i),val++);
}
}
}
Set <Character>t = m.keySet();
if(!t.containsAll(a))
return false;
else
return true;
}
public String smallestCom(Set<Character> a,String s,int length) {
int i =0;
boolean c =false ;
while(i+length-1<s.length()) {
c = compare(a,s.substring(i, i+length));
if(c==true)
break;
i++;
}
if(c==false)
return null;
else
return s.substring(i,i+length);
}
public static void main(String[] args) {
FinSmall bin = new FinSmall();
Set<Character> s = new HashSet<Character>();
s.add('a');
s.add('b');
s.add('c');
String str = "aabbcba";
String p = bin.smallestCom(s, str, 3);
System.out.println(p);
}
public boolean compare(Set<Character> a,String s) {
Map<Character,Integer> m = new HashMap<Character,Integer>();
int val=0;
for(int i =0;i<s.length();i++) {
if(a.contains(s.charAt(i))) {
if(!m.containsKey(s.charAt(i)))
m.put(s.charAt(i),1 );
else {
val = m.get(s.charAt(i));
m.put(s.charAt(i),val++);
}
}
}
Set <Character>t = m.keySet();
if(!t.containsAll(a))
return false;
else
return true;
}
public String smallestCom(Set<Character> a,String s,int length) {
int i =0;
boolean c =false ;
while(i+length-1<s.length()) {
c = compare(a,s.substring(i, i+length));
if(c==true)
break;
i++;
}
if(c==false)
return null;
else
return s.substring(i,i+length);
}
public static void main(String[] args) {
FinSmall bin = new FinSmall();
Set<Character> s = new HashSet<Character>();
s.add('a');
s.add('b');
s.add('c');
String str = "aabbcba";
String p = bin.smallestCom(s, str, 3);
System.out.println(p);
}
public boolean compare(Set<Character> a,String s) {
Map<Character,Integer> m = new HashMap<Character,Integer>();
int val=0;
for(int i =0;i<s.length();i++) {
if(a.contains(s.charAt(i))) {
if(!m.containsKey(s.charAt(i)))
m.put(s.charAt(i),1 );
else {
val = m.get(s.charAt(i));
m.put(s.charAt(i),val++);
}
}
}
Set <Character>t = m.keySet();
if(!t.containsAll(a))
return false;
else
return true;
}
public String smallestCom(Set<Character> a,String s,int length) {
int i =0;
boolean c =false ;
while(i+length-1<s.length()) {
c = compare(a,s.substring(i, i+length));
if(c==true)
break;
i++;
}
if(c==false)
return null;
else
return s.substring(i,i+length);
}
public static void main(String[] args) {
FinSmall bin = new FinSmall();
Set<Character> s = new HashSet<Character>();
s.add('a');
s.add('b');
s.add('c');
String str = "aabbcba";
String p = bin.smallestCom(s, str, 3);
System.out.println(p);
}
public boolean compare(Set<Character> a,String s) {
Map<Character,Integer> m = new HashMap<Character,Integer>();
int val=0;
for(int i =0;i<s.length();i++) {
if(a.contains(s.charAt(i))) {
if(!m.containsKey(s.charAt(i)))
m.put(s.charAt(i),1 );
else {
val = m.get(s.charAt(i));
m.put(s.charAt(i),val++);
}
}
}
Set <Character>t = m.keySet();
if(!t.containsAll(a))
return false;
else
return true;
}
public String smallestCom(Set<Character> a,String s,int length) {
int i =0;
boolean c =false ;
while(i+length-1<s.length()) {
c = compare(a,s.substring(i, i+length));
if(c==true)
break;
i++;
}
if(c==false)
return null;
else
return s.substring(i,i+length);
}
Scott's solution in Go lang:
I assume it is O(n x m), where n is length of string and m is length of set
func SearchSubstring(arr []rune, str string) string{
matchedCount := 0
hash := make(map[rune]int)
result := ""
start := 0
minLen := len(str) + 1
for i := 0 ; i < len(str); i++ {
for j, _ := range arr {
ch := rune(str[i])
if ch == arr[j] {
if hash[ch] == 0 {
matchedCount++
}
total = total + 1
hash[ch] = hash[ch] + 1
break
}
}
for matchedCount == len(arr) {
// Record substring and its length
if i - start + 1 < minLen {
minLen = i - start + 1
result = str[start: i + 1]
}
// If it is the shortest substring possible, then stop and return
if minLen == len(arr) {
return result
}
ch := rune(str[start])
if v, ok := hash[ch]; ok {
if v == 1 {
matchedCount--
}
total = total - 1
hash[ch] = hash[ch] -1
}
start++
}
}
return result
}
I'm getting to hate this problem as I'm having trouble to come up with a clean solution.
Anyway this one O(n) solution.
I think this can be cleaned up if I do not use the Queue and just the array itself.
I'll send that later once I have it.
void Main()
{
char[] p = new char[]{'a','b','c'};
string a1 = "abbcbcba";
Console.WriteLine(GetMinDistance(a1, p));
}
public static string GetMinDistance(string S, char[] P)
{
HashSet<char> hs = new HashSet<char>(P);
Dictionary<char, int> ht = new Dictionary<char, int>();
Queue<Tuple<char, int>> q = new Queue<Tuple<char,int>>();
int pos = -1;
foreach(char h in hs)
{
ht.Add(h, 0);
}
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(ht.ContainsKey(s))
{
ht[s]++;
q.Enqueue(new Tuple<char, int>(s, i));
if(hs.Contains(s))
{
hs.Remove(s);
if(hs.Count == 0)
{
pos = i;
break;
}
}
}
}
int minStart = q.Peek().Item2;
int min = pos - minStart + 1;
if(hs.Count > 0)
throw new ArgumentException("S does not contains P");
while(true)
{
Tuple<char, int> t = q.Dequeue();
ht[t.Item1]--;
bool found = false;
if(ht[t.Item1] == 0)
{
for(int i = pos + 1; i < S.Length; i++)
{
char s = S[i];
if(ht.ContainsKey(s))
{
ht[s]++;
q.Enqueue(new Tuple<char, int>(s, i));
if(s == t.Item1)
{
found = true;
pos = i;
break;
}
}
}
if(!found)
{
break;
}
}
if((pos - q.Peek().Item2 + 1) < min)
{
minStart = q.Peek().Item2;
min = pos - minStart + 1;
}
}
return S.Substring(minStart, min);
}
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void check ( char *b, string str, int len){
int l = str.length();int pos;
string sub;
char *z = new char[len+1];
for( int j=0;j<=l-len-1;j++){
pos = str.find(b);
sub = str.substr(j,len+1);
memcpy(z,sub.c_str(),sub.size());
if(strcmp(b,z)==0){
cout<<"matching substring is "<<sub<<endl;
}
}
}
void permute (char *a,string mystr, int i, int n) {
int j;
if (i == n){
check(a,mystr,n);
} else {
for(int j=i;j<=n;j++) {
swap((a+i),(a+j));
permute(a,mystr, i+1,n);
swap((a+i),(a+j));
}
}
}
int main() {
char str[]="ABC";
string mystring = "ABABBCAABACB";// You can allocate you own string.
permute(str,mystring,0,2);
return 0;
}
~
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void check ( char *b, string str, int len){
int l = str.length();int pos;
string sub;
char *z = new char[len+1];
for( int j=0;j<=l-len-1;j++){
pos = str.find(b);
sub = str.substr(j,len+1);
memcpy(z,sub.c_str(),sub.size());
if(strcmp(b,z)==0){
cout<<"matching substring is "<<sub<<endl;
}
}
}
void permute (char *a,string mystr, int i, int n) {
int j;
if (i == n){
check(a,mystr,n);
} else {
for(int j=i;j<=n;j++) {
swap((a+i),(a+j));
permute(a,mystr, i+1,n);
swap((a+i),(a+j));
}
}
}
int main() {
char str[]="ABC";
string mystring = "ABABBCAABACB";
permute(str,mystring,0,2);
return 0;
}
C++ with recursion:
#include <vector>
#include <string>
#include <iostream>
bool FindNeedleInHaystack(std::vector<char> needle, const std::string &haystack, int startHay, std::string combination)
{
std::vector<char> needleCopy(needle);
for (int i = startHay; i < haystack.length(); i++)
{
for (int j = 0; j < needle.size(); j++)
{
if (needle[j] == haystack[i])
{
if (needle.size() == 1)
{
std::cout << combination + haystack[i] << std::endl;
return true;
}
needleCopy.erase(needleCopy.begin()+j);
if (FindNeedleInHaystack(needleCopy, haystack, i + 1, combination + haystack[i]))
return true;
needleCopy = needle;
break;
}
}
if (startHay > 0)
return false;
}
return false;
}
int main(int argc, const char * argv[]) {
std::vector<char> needle = {'a', 'b', 'c'};
std::string haystack = "abbcbcbbbcabb";
FindNeedleInHaystack(needle, haystack, 0, "");
return 0;
}
function SubsetFinder(set){
this.matching = 0;
this.maxSize = set.length;
this.stack = [];
var hashSet = {};
set.forEach(function(n){
hashSet[n] = 0;
});
this.hashSet = hashSet;
}
SubsetFinder.prototype.add = function(n) {
if(this.stack.length === this.maxSize){
var removed = this.stack.shift();
if (this.hashSet[removed] !== undefined){
if(--this.hashSet[removed] === 0)
this.matching--;
}
}
this.stack.push(n);
if (this.hashSet[n] !== undefined){
if(++this.hashSet[n] === 1)
this.matching++;
}
return this.matching === this.maxSize;
};
function findSubstring(string, set){
var subsetFinder = new SubsetFinder(set);
for(var i = 0; i < string.length; i++)
if(subsetFinder.add(string[i]))
return subsetFinder.stack;
return null;
}
function SubsetFinder(set){
this.matching = 0;
this.maxSize = set.length;
this.stack = [];
var hashSet = {};
set.forEach(function(n){
hashSet[n] = 0;
});
this.hashSet = hashSet;
}
SubsetFinder.prototype.add = function(n) {
if(this.stack.length === this.maxSize){
var removed = this.stack.shift();
if (this.hashSet[removed] !== undefined){
if(--this.hashSet[removed] === 0)
this.matching--;
}
}
this.stack.push(n);
if (this.hashSet[n] !== undefined){
if(++this.hashSet[n] === 1)
this.matching++;
}
return this.matching === this.maxSize;
};
function findSubstring(string, set){
var subsetFinder = new SubsetFinder(set);
for(var i = 0; i < string.length; i++)
if(subsetFinder.add(string[i]))
return subsetFinder.stack;
return null;
}
function SubsetFinder(set){
this.matching = 0;
this.maxSize = set.length;
this.stack = [];
var hashSet = {};
set.forEach(function(n){
hashSet[n] = 0;
});
this.hashSet = hashSet;
}
SubsetFinder.prototype.add = function(n) {
if(this.stack.length === this.maxSize){
var removed = this.stack.shift();
if (this.hashSet[removed] !== undefined){
if(--this.hashSet[removed] === 0)
this.matching--;
}
}
this.stack.push(n);
if (this.hashSet[n] !== undefined){
if(++this.hashSet[n] === 1)
this.matching++;
}
return this.matching === this.maxSize;
};
function findSubstring(string, set){
var subsetFinder = new SubsetFinder(set);
for(var i = 0; i < string.length; i++)
if(subsetFinder.add(string[i]))
return subsetFinder.stack;
return null;
}
console.log(findSubstring('abbcbcba', ['a', 'b' , 'c']));
HashSet<Character> charSet = new HashSet<Character>();
String uniqueSubstring (String str) {
int total = str.length();
int setSize = charSet.size();
int index = 0;
String uniqueStr = "";
ArrayList<Character> visited = new ArrayList<Character>();
int compareCount = 0;
while (index < total) {
if (charSet.contains(str.charAt(index)) && !visited.contains(str.charAt(index))) {
visited.add(str.charAt(index));
uniqueStr += str.charAt(index);
compareCount++;
if (compareCount == setSize) return uniqueStr;
index++;
continue;
}
if (compareCount == (setSize - 1)) {
index = index - compareCount;
}
uniqueStr = "";
visited = new ArrayList<Character>();
compareCount = 0;
index++;
}
return null;
}
This problem is my kryptonite this is my cleanest iteration so far in linear time.
public static GetSmallesString(string S, HashSet<char> set)
{
var charCount = new Dictionary<char, int>();
var q = new Queue<Tuple<char, int>>();
var hSet = new HashSet<char>(set);
foreach(char c in set)
charCount.Add(c, 0);
int start = -1;
int offset = int.MaxValue;
Tuple<char, int> head = null;
Tuple<char, int> tail = null;
for(int i = 0; i < S.Length; i++)
{
char s = S[i];
if(hSet.Contains(s))
hSet.Remove(s);
if(charCount.ContainsKey(s))
{
tail = new Tuple<char, int>(s, i);
q. Enqueue(tail);
if(hSet.Count == 0)
{
head = q.Dequeue();
while(charCount[head.Item1]-- == 1)
{
hSet.Add(head.Item1);
int toffset = tail.Item2 - head.Item2 + 1;
if(toffset < offset)
{
offset = toffset;
start = head.Item2;
}
break;
}
}
}
}
if(offset == int.MaxValue)
return null;
return S.Substring(start, offset);
}
Here is a C# solution. I did use some simple Linq queries to do sorting and ordering, but these could also be implemented in the code simply.
// returns null if no match or no characters in set
string MinStringContainingSet(HashSet<char> set, string source)
{
if(set.Count == 0 || string.IsNullOrEmpty(source))
return null;
List<string> candidates = new List<string>();
// find all the candidate strings containing only characters in the set
// starting from each index position, and ensure that we have all the
// chars from the set covered
for(int i = 0; i < source.Length; i++)
{
// reset the remaining chars
HashSet<char> remaining = new HashSet<char>(set);
int end = i;
// step through characters until we hit the end or a non-matching char
while(end < source.Length && set.Contains(source[end]))
{
remaining.Remove(source[end]); // we have found this character
end++;
}
// do we have candidate that contains all the characters?
if(remaining.Count == 0)
{
// we could save a tuple containing the start index as well
// if we want to find the "first", then we would use this to stable sort
// our results
candidates.Add(source.Substring(i, end-i));
}
}
return candidates
.OrderBy(c => c.Length)
.FirstOrDefault();
}
// driver
void Main()
{
HashSet<char> set = new HashSet<char>(new char[] { 'a', 'b', 'c'});
string[] sources = new string[] {
"abbcbcba",
"caaababc",
"cabxaababc",
"xcy",
"xyzdef"
};
foreach (var source in sources)
{
System.Console.Out.WriteLine("{0} => {1}", source, MinStringContainingSet(set, source));
}
}
// Output:
// abbcbcba => cba
// caaababc => abc
// cabxaababc => cab
// xcy =>
// xyzdef =>
String find(String str, Set<Character> set) {
int idx2 = 0;
String minStr = null;
StringBuilder subStr = new StringBuilder();
Set<Character> subSet = new HashSet<Character>();
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while (idx2 < str.length()) {
while (idx2 < str.length() && !subSet.containsAll(set)) {
char nc = str.charAt(idx2);
subStr.append(nc);
subSet.add(nc);
if (map.containsKey(nc)) {
map.put(nc, map.get(nc) + 1);
}
else {
map.put(nc, 1);
}
idx2++;
}
if (idx2 == str.length() && !subSet.containsAll(set)) {
break;
}
if (subStr.length() == set.size()) {
return subStr.toString();
}
if (minStr == null || subStr.length() < minStr.length()) {
minStr = subStr.toString();
}
while (true) {
char prefix = subStr.charAt(0);
subStr.deleteCharAt(0);
map.put(prefix, map.get(prefix) - 1);
if (map.get(prefix) == 0) {
subSet.remove(prefix);
break;
}
else {
if (subStr.length() < minStr.length()) {
minStr = subStr.toString();
}
}
}
}
return minStr;
}
C solution
#include <stdio.h>
int getSetVal(char *set) {
int i=0, retVal=0;
while (*(set+i)) {
retVal |= (1 << (*(set+i) - 'a'));
i++;
}
return retVal;
}
void findSubset(char *str, char *set) {
int counter=0, i=0;
int val = getSetVal(set);
while (*(str+i) && *(str+i+1) && *(str+i+2)) {
counter |= (1<<(*(str+i) - 'a'));
counter |= (1<<(*(str+i+1) - 'a'));
counter |= (1<<(*(str+i+2) - 'a'));
if (counter == val) {
printf("found\n");
printf("%c", *(str+i));
printf("%c", *(str+i+1));
printf("%c\n", *(str+i+2));
return;
} else {
counter=0;
i++;
}
}
printf("did not find sub string\n");
}
int main() {
char *str = "abbcbcba";
char *set = "abc";
findSubset(str, set);
}
#include<iostream>
#include<string.h>
#include<map>
#include<cstring>
using namespace std;
int main()
{
string Uniq,GStr;
cout<<"Enter Unique Character"<<endl;
cin>>Uniq;
cout<<"Enter String to find the Sub string"<<endl;
cin>>GStr;
map<char,int>m;
for(unsigned int i=0;i<Uniq.length();i++)
{
m[Uniq.at(i)]=++m[Uniq.at(i)];
}
map<char,int>::iterator p;
unsigned int v=0;
unsigned int count;
for(unsigned int i=0;i<=GStr.length()-Uniq.length();i++)
{
count=0;
for(unsigned int j=i;j<i+Uniq.length();j++)
{
if(m.find(GStr.at(j))!=m.end())
{
m[GStr.at(j)]=++m[GStr.at(j)];
if(m[GStr.at(j)]==2)
{
++count;
}
else
{
for(p=m.begin();p!=m.end();p++)
{
p->second=1;
}
break;
}
}
if(count==Uniq.length())
{
for(unsigned int k=i;k<i+Uniq.length();k++)
{
cout<<GStr.at(k);
}
}
}
}
return 0;
}
#include<iostream>
#include<string.h>
#include<map>
#include<cstring>
using namespace std;
int main()
{
string Uniq,GStr;
cout<<"Enter Unique Character"<<endl;
cin>>Uniq;
cout<<"Enter String to find the Sub string"<<endl;
cin>>GStr;
map<char,int>m;
for(unsigned int i=0;i<Uniq.length();i++)
{
m[Uniq.at(i)]=++m[Uniq.at(i)];
}
map<char,int>::iterator p;
unsigned int v=0;
unsigned int count;
for(unsigned int i=0;i<=GStr.length()-Uniq.length();i++)
{
count=0;
for(unsigned int j=i;j<i+Uniq.length();j++)
{
if(m.find(GStr.at(j))!=m.end())
{
m[GStr.at(j)]=++m[GStr.at(j)];
if(m[GStr.at(j)]==2)
{
++count;
}
else
{
for(p=m.begin();p!=m.end();p++)
{
p->second=1;
}
break;
}
}
if(count==Uniq.length())
{
for(unsigned int k=i;k<i+Uniq.length();k++)
{
cout<<GStr.at(k);
}
}
}
}
return 0;
}
C++ Code
#include<iostream>
#include<string.h>
#include<map>
#include<cstring>
using namespace std;
int main()
{
string Uniq,GStr;
cout<<"Enter Unique Character"<<endl;
cin>>Uniq;
cout<<"Enter String to find the Sub string"<<endl;
cin>>GStr;
map<char,int>m;
for(unsigned int i=0;i<Uniq.length();i++)
{
m[Uniq.at(i)]=++m[Uniq.at(i)];
}
map<char,int>::iterator p;
unsigned int v=0;
unsigned int count;
for(unsigned int i=0;i<=GStr.length()-Uniq.length();i++)
{
count=0;
for(unsigned int j=i;j<i+Uniq.length();j++)
{
if(m.find(GStr.at(j))!=m.end())
{
m[GStr.at(j)]=++m[GStr.at(j)];
if(m[GStr.at(j)]==2)
{
++count;
}
else
{
for(p=m.begin();p!=m.end();p++)
{
p->second=1;
}
break;
}
}
if(count==Uniq.length())
{
for(unsigned int k=i;k<i+Uniq.length();k++)
{
cout<<GStr.at(k);
}
}
}
}
return 0;
}
Here is C++ version of solution.
This algorithm provide running time of O(N^2) where N is the length of input string.
#include <string>
#include <iostream>
#include <climits>
using namespace std;
bool isfound(string dst, string set)
{
int target = 0;
int found = 0;
int i=0, j=0;
for (i = 0; i <set.length(); i++)
target |= (1<<i);
for (int i = 0; i < dst.length(); i++)
{
for (int j = 0; j < set.length(); j++)
{
if (dst[i] == set[j])
found |= (1<<j);
}
}
return (target == found);
}
string find_minstr(string input, string set)
{
string minstr = "";
int min = INT_MAX;
int s = 0;
for(s = 0; s < input.length(); s++)
{
string line = "";
for (int i = s; i< input.length(); i++)
{
line.push_back(input[i]);
if (isfound(line, set) == true && line.length() < min)
{
min = line.length();
minstr = line;
break;
}
if (line.length() > min)
break;
}
}
return minstr;
}
This is a better algorithm that is faster than the previous one.
string find_minstr(string input, set<char> seed)
{
int min_len = INT_MAX;
string minstr="";
map<char, int> cmap;
int start = 0, count = 0, len = seed.size();
for (int i = 0 ; i < input.length(); i++)
{
int num_found = 0;
char c = input[i];
if (seed.find(c) != seed.end())
{
num_found = (cmap.find(c)!=cmap.end())? cmap[c]+1: 1;
if (num_found == 1)
count++;
cmap[c] = num_found;
}
while (count == len)
{
char s = input[start];
if (cmap.find(s) != cmap.end())
{
num_found = cmap[s];
if (num_found == 1)
count--;
cmap[s] = num_found-1;
}
if(i- start+1 < min_len)
{
minstr = input.substr(start, i-start+1);
min_len = i - start +1;
}
start++;
}
}
return minstr;
}
I added the ASCII key of the given unique characters and compare that to computed total substring's ASCII key in the given string.
public class UniqueString {
public static void main(String[] args) {
string("acbacbbbc", "abc");
}
private static void string(String string, String ch ) {
char []cha = ch.toCharArray();
int s=0,c =0;
String tem="";
for (int i = 0; i < cha.length; i++) {
s+=cha[i];
}
for (int i = 0; i < string.length()-ch.length(); i++) {
tem = (string.substring(i, (i+ch.length())));
for (int j = 0; j < tem.length(); j++) {
c +=tem.charAt(j);
}
if(s==c){
System.out.println(tem);
break;
}
else{
c=0;
}
}
}
}
public class UniqueSubstring {
public static String unique;
public static void main(String[] args){
String prob = "fasdnavnvbffdscfsd";
uniqueChars(prob);
System.out.println("Unique : "+unique);
System.out.println("Min SubString : "+minUniqSubstring(prob));
}
public static String minUniqSubstring(String prob) {
String ans = "";
int i = unique.length();
while (i <= prob.length()) {
for (int j = 0; j <= prob.length() - i; j++) {
if (isContainsUnique(prob.substring(j, j + i))) {
return prob.substring(j, j + i);
}
}
i++;
}
return ans;
}
public static boolean isContainsUnique(String substr){
for(int i = 0; i < unique.length(); i++){
boolean flag = false;
for(int j = 0; j < substr.length(); j++){
if(unique.charAt(i) == substr.charAt(j)){
flag = true;
}
}
if(!flag){
return false;
}
}
return true;
}
public static void uniqueChars(String prob){
unique = "";
boolean[] char_set = new boolean[128];
for(int i = 0; i < prob.length(); i++){
int val = prob.charAt(i);
if(!char_set[val]) {
unique += prob.charAt(i);
}
char_set[val] = true;
}
return;
}
}
public class UniqueSubstring {
public static String unique;
public static void main(String[] args){
String prob = "fasdnavnvbffdscfsd";
uniqueChars(prob);
System.out.println("Unique : "+unique);
System.out.println("Min SubString : "+minUniqSubstring(prob));
}
public static String minUniqSubstring(String prob) {
String ans = "";
int i = unique.length();
while (i <= prob.length()) {
for (int j = 0; j <= prob.length() - i; j++) {
if (isContainsUnique(prob.substring(j, j + i))) {
return prob.substring(j, j + i);
}
}
i++;
}
return ans;
}
public static boolean isContainsUnique(String substr){
for(int i = 0; i < unique.length(); i++){
boolean flag = false;
for(int j = 0; j < substr.length(); j++){
if(unique.charAt(i) == substr.charAt(j)){
flag = true;
}
}
if(!flag){
return false;
}
}
return true;
}
public static void uniqueChars(String prob){
unique = "";
boolean[] char_set = new boolean[128];
for(int i = 0; i < prob.length(); i++){
int val = prob.charAt(i);
if(!char_set[val]) {
unique += prob.charAt(i);
}
char_set[val] = true;
}
return;
}
}
in python
def shortest_substring(s, char_set):
substring = set()
n = 0
for c in s:
substring.add(c)
n += 1
if substring == char_set:
n = s[0:n]
m = shortest_substring(s[1:], char_set)
return n if m is None or len(n) <= len(m) else m
return None
print shortest_substring('caaababc', set(['a', 'b', 'c']))
Is this solution O(n^2)? n is the length of the string
n = the shortest substring starts at 0
m = the shortest substring in s[1:] (not necessary starts at 1)
use shorter one from n and m
recursive solution
public static void main(String[] args) {
FinSmall bin = new FinSmall();
Set<Character> s = new HashSet<Character>();
s.add('a');
s.add('b');
s.add('c');
String str = "aabbcba";
String p = bin.smallestCom(s, str, 3);
System.out.println(p);
}
public boolean compare(Set<Character> a,String s) {
Map<Character,Integer> m = new HashMap<Character,Integer>();
int val=0;
for(int i =0;i<s.length();i++) {
if(a.contains(s.charAt(i))) {
if(!m.containsKey(s.charAt(i)))
m.put(s.charAt(i),1 );
else {
val = m.get(s.charAt(i));
m.put(s.charAt(i),val++);
}
}
}
Set <Character>t = m.keySet();
if(!t.containsAll(a))
return false;
else
return true;
}
public String smallestCom(Set<Character> a,String s,int length) {
int i =0;
boolean c =false ;
while(i+length-1<s.length()) {
c = compare(a,s.substring(i, i+length));
if(c==true)
break;
i++;
}
if(c==false)
return null;
else
return s.substring(i,i+length);
}
public String findMin (String s, HashSet<Character> set){ int len = set.size() , count = 0 , tail = 0 , minLen = Integer.MAX_VALUE; String result = "" ; HashMap<Character, Integer> map = new HashMap<> (); for (int i = 0 ; i < s.length() ; ++i) { char ch = s.charAt(i) ; if (set.contains(ch)) { int c = map.containsKey(ch) ? map.get(ch) + 1 : 1 ; if (c == 1) count++; map.put(ch, c) ; } while (count == len) { if (set.contains(s.charAt(tail))) { int v = map.get(s.charAt(tail)); if (v - 1 == 0) { count--; } map.put(s.charAt(tail), v - 1) ; } if (i - tail + 1 < minLen) { minLen = i - tail + 1 ; result = s.substring(tail, i + 1) ; } tail++; } } return result;}
- Scott February 04, 2015