Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
bool isAlphabetChar(char a)
{
return dict[a];
}
//time complexity of 2 * input size
//extra storage is input size
string shortestSub (string input)
{
vector<bool> isAlphabet(input.size());
for (int i=0; i< input.size(); i++)
{
if (isAlphabetChar(input[i]))
{
isAlphabet[i] = 1;
}
}
//keeps track of shortest start index and shortest length
int startIndex = 0;
int length = input.size();
//if in the middle of evaluating a string, set to true
bool evalString = true;
int currentLength = 0;
int currentStart = 0;
for (int i=0; i< isAlphabet.size(); i++)
{
if (isAlphabet[i] == 1)
{
if (evalString == false)
{
currentStart = i;
}
evalString = true;
currentLength++;
}
else
{
if (evalString == true)
{
if (currentLength < length)
{
length = currentLength;
startIndex = currentStart;
}
}
evalString = false;
currentLength = 0;
currentStart = i;
}
}
return input.substr(startIndex, length);
}
/*
The idea is to isolate all pair of (start,end) indices
such that : length is >= alphabet
sort ascending by length
then find first match - that will ensure shortest.
There are other alternatives.
just find pairs, ignore all which are less than size of alphabet, and keep a min.
This avoids the sorting.
*/
def find_min_alpha_sub_str( string , alphabet ){
r = [0:size(string)]
max_len = size(alphabet)
pairs = join ( r , r ) :: { $.o.1 - $.o.0 + 1 >= max_len }
fold( pairs , string ) :: {
s = string[$.o.0:$.o.1]
// ignore when not a sub set or current size is >= min size
continue ( !( alphabet.value <= s.value && size(s) < size($.p) ) )
$.p = s // got the min one
}
}
s = find_min_alpha_sub_str ( "abbcac", "abc" )
println( s )
/* @author prizkaboom
*/
public class ShortestSubstring {
HashMap HashAlphabet;
public ShortestSubstring()
{
}
void resetAlphabet()
{
HashAlphabet = new HashMap();
}
public void getShortestSubstring(String stringToCheck, String Alphabet )
{
this.resetAlphabet();
int initIndex=-1;
int lastIndex=-1;
for (int i = 0; i < stringToCheck.length(); i++)
{
char c = stringToCheck.charAt(i);
if(HashAlphabet.containsKey(c))
{
resetAlphabet();
initIndex=i+1;
}
else
{
HashAlphabet.put(c,i);
}
System.out.println("Adding:"+c);
if(HashAlphabet.size()==Alphabet.length())
{
if(ContainsAlphabet(Alphabet))
{
lastIndex=i+1;
String subs=stringToCheck.substring(initIndex,lastIndex);
System.out.println("is:"+ subs);
printHashAlphabet();
return;
}
else
{
resetAlphabet();
initIndex=i+1;
}
}
if(HashAlphabet.size()>Alphabet.length())
{
resetAlphabet();
initIndex=i+1;
}
}
// printHashAlphabet();
System.out.println("The alphabet:"+Alphabet+" is not contained on this string");
// If the ford end but we arribe here if meas that the shortest alphabet is no present
}
boolean ContainsAlphabet(String Alphabet)
{
// Add of elements of the Alphabet
for (int i = 0; i < Alphabet.length(); i++)
{
char c = Alphabet.charAt(i);
if(!HashAlphabet.containsKey(c))
{
return false;
}
}
return true;
}
void printHashAlphabet()
{
System.out.println("Map : " + HashAlphabet+ "This can track the position!!");
}
class Program
{
static void Main(string[] args)
{
string inputString = "aabbccba";
char[] searchedCharacters = {'a','b','c'};
string tempStr = "";
int startingSize = 3;
int maxLength = inputString.Length;
bool found = true;
while (startingSize <= maxLength)
{
for (int i = 0; i <= maxLength-startingSize; i++)
{
tempStr = inputString.Substring(i, startingSize);
found = true;
foreach (char searchedChar in searchedCharacters)
{
if (tempStr.IndexOf(searchedChar) == -1)
{
found = false;
break;
}
}
if (found)
{
Console.WriteLine(tempStr);
Console.Read();
return;
}
}
startingSize++;
}
}
}
}
O(n^2)
public class ShortestSubstringWithAllAlphabets {
public static void main(String[] args){
String oStr = "aabbccba";
char[] cArr = {'a', 'b', 'c'};
String subStr=null;
int min = Integer.MAX_VALUE;
for(int i=0; i<oStr.length(); i++){
for(int j=i+cArr.length-1; j<oStr.length(); j++){
String sStr = oStr.substring(i, j+1);
if(containAll(sStr, cArr)){
if(sStr.length()<min){
subStr = sStr;
min = sStr.length();
}
break;
}
}
}
System.out.println(subStr+": "+min);
}
public static boolean containAll(String str, char[] cArr){
boolean containAll = true;
Set<Character> cSet = new HashSet<Character>();
for(int i=0; i<str.length(); i++){
cSet.add(str.charAt(i));
}
for(int j=0; j<cArr.length; j++){
if(!cSet.contains(cArr[j])) return false;
}
return containAll;
}
}
/*I'm sure this can be optimized further but I'm pasting it for others to get ideas from
The idea here is finding segments in the master string that contain all the characters of the alphabet string(to remove) and then shrinking the master string 1 character at a time*/
class Program
{
static void Main(string[] args)
{
String str = "aabbccba";
String ab = "abc";
StringBuilder sbr = new StringBuilder(str);
//Console.WriteLine(str.Substring(0));
for (int i = 0; i < sbr.Length; i++)
{
FindSubstring(str.Substring(i), ab);
FindSubstring(str.Substring(0, str.Length - i),ab);
}
//FindSubstring(str, ab);
//sbr.Remove(1, 1);
Console.WriteLine("{0}", sbr.ToString());
Console.ReadLine();
}
public static void FindSubstring(String str, String ab)
{
StringBuilder sbr = new StringBuilder(str);
StringBuilder abSbr = new StringBuilder(ab);
int wordStart = 0;
for(int i = 0; i < sbr.Length; i++)
{
for(int x = 0;x<abSbr.Length;x++)
{
char iChar = sbr[i];
char xChar = abSbr[x];
if (iChar==xChar)
{
abSbr.Remove(x, 1);
break;
}
}
if (abSbr.Length == 0)
{
Console.WriteLine(sbr.ToString(wordStart, i - wordStart+1));
abSbr = new StringBuilder(ab);
wordStart = i;
}
}
}
}
Steps
1)get unique set of characters, using hash or simple arr[26]
2) Suppose N is the length of unique character set. Find sum1 of the unique char set, assuming a=1, b=2...so on.
3)Now , pick every N length set from input, get its sum2, and compare it with unique set sum1. If sum1!=sum2 , sum2=sum2-input[i]+input[i+N].. and proceed like a moving window.
4)if sum1==sum2, use an utility to compare if the two strings are anagram.
continue, till i==strlen(input)-N+1 or you find the answer.
Here's my solution.
I think it is O(n) time and O(n) space, but feedback is appreciated.
//Find shortest string with all chars in alphabet
//
//For BigO notation, these values are used
//a = length of alphabet
//b = length of input string
//c = number of alphabet letters in input string. max is 'b' if only using alphabet chars
//
//Time
//O(a) + O(b * a) + O(a) + O(c * a) + O(a)
//a is fixed 1 to 26 for alphabet (or upper end of 256 if using entire ASCII char set)
//b is 1...n
//c is count of a in b, with upper bound of b, so 1...n
//
//= O(26) + O(n * 26) + O(26) + O(n * 26) + O(26)
//= O(2 (n * 26))
//= O(n)
//
//Space
//O(a) Hash table for alphabet
//O(c * a) Hash table for each alphabet letter in input string
//= O(26) + O(n * 26)
//= O(n)
public static string FindShortestStringWithAlphabet(string input, string alphabet)
{
//Sample Input
// ADOBECODEBANC <- Input string
// 0123456789111 <- Input index
// 012
//
// ABC <- Input Alphabet
// A 0, 10 <- Index values of A, B, C in input string
// B 3, 9
// C 5, 12
//Find minimum distance between A, B, C
//
// For each character in the alphabet, we need to find the nearest char for every other item in the alphabet
// Then we find the difference between the minimum and maximum index for each item in the alphabet
//
// For example, the index of the alphabet input chars are below, along with the nearest A, B, C characters
//
// 0 3 5 9 10 12
// A B C B A C
// |
// A nearest B = 3 (index)
// nearest C = 5 (index)
// current A = 0
// total = 5-0 = 5 <-- Max(A, B, C) = Max (0, 3, 5) = 5
// Min(A, B, C) = Min(0, 3, 5) = 0
// = Abs(0 - 5) = 5
// |
// B nearest A = 0
// nearest C = 5
// current B = 3
// total = 5-0 = 5
//
// |
// C nearest A = 0, 10
// nearest B = 3
// current C = 5
// total = 0 -> 3 -> 5 = 5 || 3 -> 5 -> 10 = 7 --> 5
//
// |
// B nearest A = 10
// nearest C = 12
// current B = 9
// total = 9 - 12 = 3 <--- Solution
//
// |
// A nearest B = 9
// nearest C = 12
// current A = 10
// total = 9 - 12 = 3 <--- Solution All 3 are the solution since they are different letters of the alphabet
//
// |
// C nearest A = 10
// nearest B = 9
// current C = 12
// total = 9 - 12 = 3 <--- Solution
//
// Minimum substring length = 3
// Starting = 9
// Ending = 12
// return: BANC
//charMap stores the index of the items in the alphabet
Dictionary<int, Item> charMap = new Dictionary<int, Item>();
//alphabetMap stores the characters in the alphabet for O(1) lookup to find if a character is in the alphabet
//It also stores the last index of the character when scanning the input left to right or right to left
Dictionary<char, int> alphabetMap = new Dictionary<char, int>();
//charMapStack stores the order we find the items in the input so we can re-process them in reverse to find the closest
//character that may appear after the character. When processing left to right, we scan all elements. But when we scan
//right to left, we only have to look at alphabet elements, so we only have to look at the items in the stack
Stack<int> charMapStack = new Stack<int>();
// O(a)
//Initalize the alphabetMap and set chars to -1 indicating no values have been seen
for (int i = 0; i < alphabet.Length; i++)
{
if (alphabetMap.ContainsKey((alphabet[i])))
continue;
alphabetMap.Add(alphabet[i], -1);
}
//Itterate over the input from left to right
//If the character is in the alphabet
// 1. add this index position to the charMap hash
// 2. set the alphabetMap last seen location for this character as the current index
// 3. copy the last location for each character into the charMap.nearestChar hash map
// 4. push the current index number onto the charMapStack for the return trip in processing right to left
// we use this so we don't have to process every character on the return trip. we only have to process
// those that are in the alphabet
//O(b)
for (int x = 0; x < input.Length; x++)
{
if (alphabetMap.ContainsKey(input[x]))
{
charMap.Add(x, new Item(input[x], x));
alphabetMap[input[x]] = x; //set this char as nearest
//O(a)
foreach (var i in alphabetMap.Keys)
{
//Add all keys, even if it is -1
charMap[x].nearestChar.Add(i, alphabetMap[i]);
}
charMapStack.Push(x);
}
}
//First pass is complete and the charMap.nearestChar is populated with the nearest character that occured before that
//value in the index. The next step is to go from right to left and populate the nearest characters going this direction
//reset alphabetMap to -1 for return trip
alphabetMap = new Dictionary<char, int>();
//O(a)
for (int i = 0; i < alphabet.Length; i++)
{
if (alphabetMap.ContainsKey((alphabet[i])))
continue;
alphabetMap.Add(alphabet[i], -1);
}
//Store solution index as minIndex
int minIndex = -1;
//O(c)
//Pop an item off the stack and process it until the stack is empty
while (charMapStack.Count > 0)
{
//x is the key value inside charMap. It is not the index of the value in the input string unless
//the input string only contains characters from the alphabet
int x = charMapStack.Pop();
char c = charMap[x].C;
int index = charMap[x].Index; //index is the actual index value inside the input string
//Initialize charMap
charMap[x].Size = 0; //stores the final size (max index - min index)
charMap[x].MinChar = index; //init minChar to current index
charMap[x].MaxChar = index; //init maxChar to current index
//update alphabetMap with current character and index position
alphabetMap[c] = index;
//O(a)
foreach (char v in alphabetMap.Keys)
{
//Check to see if we have a value in the map
if (alphabetMap.ContainsKey(v) && alphabetMap[v] != -1)
{
//if our current nearest is -1, or the new value is < current value, update it
if (charMap[x].nearestChar[v] == -1 ||
alphabetMap[v] < charMap[x].nearestChar[v])
{
charMap[x].nearestChar[v] = alphabetMap[v];
}
}
//Check to see if this character is still -1
//If so, then this alphabet character was not found in the forward or reverse
//processing of the input, so the character does not exist.
//Return empty string for failure
if (charMap[x].nearestChar[v] == -1)
{
return string.Empty;
}
//At this point charMap.nearestChar[v] has been processed forwards and backwards and contains the closest
//character for character 'v'
//So, check to see if its index is the Min or Max for the nearest alphabet characters
charMap[x].MinChar = Math.Min(charMap[x].MinChar, charMap[x].nearestChar[v]);
charMap[x].MaxChar = Math.Max(charMap[x].MaxChar, charMap[x].nearestChar[v]);
}
//All chracters have been processed forwards and backwards and the Min and Max character is know
//We can now calculate the size of the window using the Min and Max values
charMap[x].Size = charMap[x].MaxChar - charMap[x].MinChar;
//Check to see if we found a new minimum
if (minIndex < 0)
minIndex = x;
else if (charMap[x].Size < charMap[minIndex].Size)
minIndex = x;
}
//Finally find the min and max indexes in the solution set.
int start = int.MaxValue;
int end = int.MinValue;
//O(a)
foreach (var key in charMap[minIndex].nearestChar.Keys)
{
start = Math.Min(start, charMap[minIndex].nearestChar[key]);
end = Math.Max(end, charMap[minIndex].nearestChar[key]);
}
//Create substring using min and max index values
string ret = input.Substring(start, end-start+1);
return ret;
}
public class Item
{
public char C { get; set; }
public int Index { get; set; }
public Dictionary<char, int> nearestChar { get; set; }
public int MinChar { get; set; }
public int MaxChar { get; set; }
public int Size { get; set; }
public Item(char c, int index)
{
C = c;
Index = index;
nearestChar = new Dictionary<char, int>();
}
}
/*Sliding window concept
Slide a window over the string
abcbbad-->[WINDOW]-->abbbcaa
we build an array containing letters found in the window
store window start, end index in $windowStart and $windowEnd
If our window contain $minAlphabet contained in aLetterFound! Fabulous...
increase windowStart... if we have the same letter as previously (we have a shorter string)... drop the letter...
increase windowEnd to get the missing letter
*/
$inputString="aabbccba";
$minAlphabet = ['a','b','c'];
$string = getShortestSubstring($inputString,$minAlphabet);
echo "Shortest string :".$string.PHP_EOL;
function getShortestSubstring($input,$minAlphabet)
{
$aLetterFound = [];//array containing found letters
$minSize = false;//the smallest substring
$windowStart = 0;//Window position
$windowEnd = 0;
$len = strlen($input);//string length
$bestString="";//best string found
//termination condition
while($windowStart<$len)
{
//index are the same... ok increase window size
if($windowStart==$windowEnd)
{
if($windowEnd<$len-1)
$windowEnd++;
}
$currentLetterStart = $input[$windowStart];
$currentLetterEnd = $input[$windowEnd];
//same letter for start and end.... found letter unchanged...
//increase start index
if($currentLetterStart==$currentLetterEnd){
$windowStart++;
continue;
}
//Ok, we have found a new letter (start of the window)
if(!array_key_exists($currentLetterStart,$aLetterFound))
{
$aLetterFound[$currentLetterStart]=$windowStart;
}
//Ok, we have found a new letter (end of the window)
if(!array_key_exists($currentLetterEnd,$aLetterFound))
{
$aLetterFound[$currentLetterEnd]=$windowEnd;
}
//Wo oh ! We have everything
if(count($aLetterFound) == count($minAlphabet))
{
//first substring found or we find an another...
if($minSize===false || ($windowEnd-$windowStart)<$minSize){
$minSize = $windowEnd-$windowStart;
$bestString = substr($input,$windowStart,$minSize+1);
}
//drop the letter from start and shift our start window position
unset($aLetterFound[$currentLetterStart]);
$windowStart++;
continue;
}
//We have nothing
//at the end of our string => slide our window : start index
if($windowEnd==$len-1)
$windowStart++;
//slide our window : end index
if($windowEnd<$len-1)
$windowEnd++;
}
return $bestString;
}
Here's a java solution.
public static void main(String[] args)
{
String problem = "aabbczxcbbca";
String given = "abc";
boolean answer = false;
ArrayList<Integer> indexes = new ArrayList();
int count = given.length();
for(int i = 0; i < problem.length() ; i++)
{
String c = Character.toString(problem.charAt(i));
System.out.println("Now comparing : " + c);
if(given.contains(c))
{
if(indexes.contains(given.indexOf(c)))
{
indexes.clear();
count = given.length();
System.out.println("**CLEARING INDEXES (top)**");
}
indexes.add(given.indexOf(c));
System.out.println("Adding to indexes: " + given.indexOf(c));
count--;
if(count == 0)
{
answer = true;
break;
}
}
else
{
indexes.clear();
System.out.println("**CLEARING INDEXES**");
count = given.length();
}
}
System.out.println(answer);
}
static String shortestSubstring(String input, char[] alphabet) {
Set<Character> usedChars = new HashSet<>();
boolean hasSubstringFound = false;
int start = 0, end = input.length();
for (int i = 0; i < input.length(); i++) {
for (; i < input.length() - 1 && input.charAt(i) == input.charAt(i + 1); i++) {
}
int j = i;
for (; usedChars.size() < alphabet.length && j < input.length(); j++) {
char current = input.charAt(j);
usedChars.add(current);
}
if (usedChars.size() == alphabet.length && end - start > j - i) {
hasSubstringFound = true;
start = i;
end = j;
}
usedChars.clear();
}
return hasSubstringFound ? input.substring(start, end) : null;
}
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
string in, sub;
cin >> in >> sub;
unordered_map<char, int> char_count;
queue<char> char_order;
unordered_set<char> chars;
for (int i = 0; i < sub.size(); ++i) chars.insert(sub[i]);
int min_l = in.size();
int start_pos = 0;
for (int i = 0; i < in.size(); ++i) {
const char ch = in[i];
char_order.push(ch);
auto it = char_count.find(ch);
if (it != char_count.end()) {
it->second++;
} else if (chars.count(ch) > 0) {
char_count[ch] = 1;
}
if (char_count.size() == chars.size()) {
while (char_count.size() == chars.size()) {
char top = char_order.front();
char_order.pop();
auto it = char_count.find(top);
if (it != char_count.end()) {
it->second--;
if (it->second == 0) {
char_count.erase(it);
}
}
}
if (min_l > char_order.size() + 1) {
min_l = char_order.size() + 1;
start_pos = i - min_l + 1;
}
}
}
cout << in.substr(start_pos, min_l) << endl;
return 0;
}
public String printString(String input, String alphabet)
{
String result = "";
int length = alphabet.length();
// ^ matches the start of the string
// (?: open a non capturing group
// ([alphabets]) The characters that are allowed the found char is captured in group 1
// (?!.*\\1) That character is matched only if it does not occur once more
// ){length} Defines the amount of characters
// $ matches the end of the string
String REGEX = "^(?:([" +alphabet + "])(?!.*\\1)){" + (length) +"}$";
Pattern p = Pattern.compile(REGEX);
int inputLength = input.length();
for(int i = 0 ; i < (inputLength - length + 2);i++)
{
result = input.substring(i, i+length);
if(p.matcher(result).find())
{
return result;
}
}
return result;
}
Here is my solution
def shortest_substring(inp, alphabet):
start, end = 0, 1
alphabet = set(alphabet)
result = None
while start < len(inp) and end < len(inp):
current = inp[start:end]
if set(current).issuperset(alphabet):
if result is None:
result = current
else:
result = min([result, current], key=len)
start += 1
else:
end += 1
return result
This is my solution using 2 histograms with start and end pointer O(n+c)
sti = raw_input().strip()
dct = raw_input().strip()
h_dct = dict()
h_sti = dict()
# creating histogram for the dictionary (to compare)
for i in dct:
h_dct[i] = 1 if i not in h_dct else h_dct[i]+1
# compare two histograms to validate using the dictionary as base
def checkwindow():
global h_dct, h_sti
for i in h_dct.keys():
if i not in h_sti:
return False
if(h_sti[i]<h_dct[i]):
return False
return True
def histog_add(elem,v):
global h_dct, h_sti
if(elem not in h_dct):
return
if(v>0):
h_sti[elem] = 1 if elem not in h_sti else h_sti[elem]+1
else:
if(elem in h_sti):
h_sti[elem]-=1
i=0 # start pointer
j=0 # end pointer
lstr = ""
while( i < len(sti) ):
if(checkwindow()):
lstr = sti[i:j]
# move i pointer to the right
histog_add(sti[i],-1)
i+=1
continue
if(j<len(sti)): # move j pointer to the right
histog_add(sti[j],1)
j+=1
else: # move i pointer to the right
histog_add(sti[i],-1)
i+=1
print("->" + sti[i:j])
print lstr
import java.util.*;
public class SubStringLetters {
public static void main(String[] args) {
System.out.println(findSubString("aabbccba"));
System.out.println(findSubString("abbcac"));
}
public static String findSubString(String input) {
String result = input;
Set<Character> set = new HashSet<Character>();
char[] charArr = input.toCharArray();
for (int i = 0; i < charArr.length; i++) {
if (!set.contains(charArr[i])) {
set.add(new Character(charArr[i]));
}
}
int size = set.size();
Character previous = null;
for (int i = 0; i < charArr.length; i++) {
Character current = new Character(charArr[i]);
if (previous == null) {
previous = current;
} else if (!current.equals(previous)) {
String subString = findSubStringFromI(charArr, i - 1, size);
if (subString != null && subString.length() < result.length()) {
result = subString;
}
}
}
return result;
}
public static String findSubStringFromI(char[] charArr, int k, int setSize) {
StringBuilder sb = new StringBuilder("");
Set<Character> set = new HashSet<Character>();
for (int i = k; i < charArr.length; i++) {
Character c = new Character(charArr[i]);
if (set.size() < setSize) {
set.add(c);
sb.append(charArr[i]);
} else {
break;
}
}
if (set.size() < setSize) {
return null;
}
return sb.toString();
}
}
class Occupied {
int from;
int to;
Occupied(int from, int to) {
this.from = from;
this.to = to;
}
}
This approach applies run length encoding first and then seeks for all abc combinations in the end and stores the one which has minimal length.
s="aabbccba"
def runl(s):
news=""
count=1
i=1
while i<len(s):
if s[i]==s[i-1]:
count+=1
else:
news+=str(count)+s[i-1]
count=1
i+=1
news+=str(count)+s[i-1]
return news
def getstr(s):
result=s
i=1
while i+4<len(s):
temp=s[i]+s[i+2]+s[i+4]
if temp in ["abc","acb","bac","bca","cab","cba"]:
string=s[i]+s[i+2]*int(s[i+1])+s[i+4]
if len(string)<len(result):
result=string
i+=2
return result
print getstr(runl(s))
public String matchingString(String input, String alphabet) {
if (TextUtil.isEmpty(input) || TextUtil.isEmpty(alphabet)) return “”;
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < input.length(); i++) {
if (hs.contains(input.charAt(i))) {
hs = new HashSet<>();
}
hs.add(input.charAt(i));
if (hm.size() == alphabet.length()) {
return input.substring(i - alphabet.length(), alphabet.length());
}
}
}
1. We can capture the indexes of each character in the pattern
2. then find the range with minimum difference between start and end of the range
- pick the first occurrence of each character pick the min and max
- drop the min and pick the next element from the queue it was dropped
repeat 2 until one of the source exhausts
3. return the range with minimum difference.
void min_substring(string str, string mat) {
unordered_set<char> os;
for(int i = 0; i < mat.length(); i++) {
os.insert(mat[i]);
}
stack<pair<int, string> > st;
set<char> count_set;
// now use the sliding window
int start = 0;
for(int i = 0`; i <str.length(); i++) {
if(os.find(str[i]) != os.end()) {
// match
if (i != start && str[i] == str[start]) {
// just expand the
start++;
} else {
// see it it completes the search characters
if(count_set.find(str[i]) == count_set.end()) {
// new character
count_set.insert(str[i]);
if(count_set.size() == mat.length()) {
// found all the matching
if (st.top().first > (i-start+1)) {
st.pop();
st.push(pair<int, string>((i-start+1),
str.substr(start, i+1)));
}
count_set.erase(str[start]);
start++;
}
}// if already seen character, just increament i, keep starts
// as it is
}
}
}
if(!st.empty()) {
cout << "min string is " << st.top().second << " of length " << st.top().first;
}
}
public static void main(String[] args)
{
String inputString = "aabbccba";
char[] searchedCharacters = {'a','b','c'};
int startingSize = searchedCharacters.length;
int maxLength = inputString.length();
int searchSize = startingSize;
String tempStr = "";
boolean found;
while (startingSize <= maxLength)
{
for (int i = 0; i <= maxLength-searchSize; i++, startingSize++)
{
tempStr = inputString.substring(i, startingSize);
found = true;
for (char searchedChar:searchedCharacters)
{
if (tempStr.indexOf(searchedChar) == -1)
{
found = false;
break;
}
}
if (found)
{
System.out.println(tempStr);
return;
}
}
}
}
public static void main(String[] args)
{
String inputString = "aabbccba";
char[] searchedCharacters = {'a','b','c'};
int startingSize = searchedCharacters.length;
int maxLength = inputString.length();
int searchSize = startingSize;
String tempStr = "";
boolean found;
while (startingSize <= maxLength)
{
for (int i = 0; i <= maxLength-searchSize; i++, startingSize++)
{
tempStr = inputString.substring(i, startingSize);
found = true;
for (char searchedChar:searchedCharacters)
{
if (tempStr.indexOf(searchedChar) == -1)
{
found = false;
break;
}
}
if (found)
{
System.out.println(tempStr);
return;
}
}
}
}
class Lab {
static String s1 ="abc";
static String result="";
public static void main(String []args){
String s="abbcac";
int l=s1.length();
int i=0;
boolean b;
while(l<=s.length()){
String ss=s.substring(i, l);
b= check(ss);
i++;
l++;
}
System.out.println("Hello check"+"\t"+result);
}
public static boolean check(String s){
char ch[] =s1.toCharArray();
char ch2[] =s.toCharArray();
int count=0;
System.out.println(s);
boolean b=false;
for(int i=0;i<ch2.length;i++){
b=false;
for(int j=0;j<ch2.length;j++){
if(ch[i]==ch2[j]){
b=true;
}
}
if(b){
count++;
}
}
if(count==s.length()){
result=s;
}
return false;
}
}
class Lab {
static String s1 ="abc";
static String result="";
public static void main(String []args){
String s="abbcac";
int l=s1.length();
int i=0;
boolean b;
while(l<=s.length()){
String ss=s.substring(i, l);
b= check(ss);
i++;
l++;
}
System.out.println("Hello check"+"\t"+result);
}
public static boolean check(String s){
char ch[] =s1.toCharArray();
char ch2[] =s.toCharArray();
int count=0;
System.out.println(s);
boolean b=false;
for(int i=0;i<ch2.length;i++){
b=false;
for(int j=0;j<ch2.length;j++){
if(ch[i]==ch2[j]){
b=true;
}
}
if(b){
count++;
}
}
if(count==s.length()){
result=s;
}
return false;
}
}
O(n), no extra space.
public static String shortest(String input) {
if (input == "" || input == null) return "";
int sequenceStart = -1;
int minStart = -1;
int minLength = Integer.MAX_VALUE;
for (int current = 1; current < input.length(); current++) {
if (input.charAt(current - 1) != input.charAt(current)) {
if (sequenceStart == -1) {
sequenceStart = current - 1;
} else {
int len = current - sequenceStart + 1;
if (len < minLength && input.charAt(current) != input.charAt(sequenceStart)) {
minStart = sequenceStart;
minLength = len;
}
sequenceStart = -1;
current--;
}
}
}
if (minStart == -1)
return "";
else
return input.substring(minStart, minStart + minLength);
}
- prathak07 January 25, 2017