Morgan Stanley Interview Question
Java DevelopersCountry: India
Interview Type: Written Test
Tried to implement the solution provided by Kishore.
public static void findShortestSubString() {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
Set<String> results = new HashSet<String>();
// 1. split the s1 with s3
// 2. sp rstrupv wrpts
// 3. find the shortest word that has s2 in it.
// -- if word's length >= s2.length --> find the shortest word sequence containing s2
String[] stringsToFind = s1.split(s3);
for(String stringToFind : stringsToFind)
{
// ignore shorter strings
if( stringToFind.length() < s2.length() )
{
continue;
}
// ignore the words that dont have every characters present in s2
if( !stringHasAllLetters(stringToFind, s2))
{
continue;
}
boolean subStringFound = false;
int offset = 0;
int i = 0;
// start with the exact length
while( !subStringFound )
{
// start to find all characters of s2 within equal length of words in stringToFind,
// if not found, increase length each time
for(i=0; i <= (stringToFind.length() - s2.length() - offset); i++ )
{
String currentSegment = stringToFind.substring(i, i + s2.length() + offset);
if( stringHasAllLetters(currentSegment, s2) )
{
results.add(currentSegment);
subStringFound = true;
break;
}
}
if( !subStringFound )
{
i = 0;
offset++;
}
}
}
System.out.println(results);
}
private static boolean stringHasAllLetters(String stringToFind, String letters)
{
boolean allLettersPresent = true;
for(char c : letters.toCharArray())
{
if(stringToFind.indexOf(c) == -1){
allLettersPresent = false;
break;
}
}
return allLettersPresent;
}
I’m going to propose a linear time solution here.
Concept is to
1. Eliminate all characters of s3 from s1
2. Find the first subsequence of s1 that contains all chars of s2
Create a bool array of 256 chars a[256]
Walk S3, char by char, for each char c set a[c] = TRUE
Walk S1, and if for any char c of S1, a[c] == TRUE, means this char is also present in S3, so delete it
Now , create another bool array of 256 chars b[256]
Walk S2, char by char, for each char c set b[c] = TRUE
Walk S1, and if for any char c , b[c] == TRUE, means this char is present both in S1 & S2 and not S3.
So, put this aside into a string (S)
At the end, S will give us the answer
Hi Puneet, I was answering in an online interview to this question and followed your algorithm but then realised that its wrong. Please don't post wrong answers. Thankfully program from Kishor Kumar saved my day
Girish, I didn't post this algorithm knowing that it is wrong. When I post answer, I know they're correct as far as I know.
Can you tell me whats wrong with it?
hey puneet.. nothing offensive here.. I just tried following your algorithm blindly as I had only 15 min to solve but couldn't get the desired answer.. better I post my code here.. may be I am wrong here.. you can help me out where I went wrong.. thanks :-)
boolean[] barray = new boolean[256];
for(int i=0;i<str3.length();i++)
{
char c= str3.charAt(i);
barray[c] = true;
}
for(int i=0;i<str1.length();i++)
{
if (barray[str1.charAt(i)]== true)
str1=str1.replaceAll(Character.toString(str1.charAt(i)), "");
}
System.out.println(str1);
boolean[] bary = new boolean[256];
for(int i=0;i<str2.length();i++)
{
char c= str2.charAt(i);
bary[c] = true;
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<str1.length();i++)
{
if (bary[str1.charAt(i)]== true)
sb.append(str1.charAt(i));
}
System.out.println(sb.toString());
As I said, I blindly followed your steps without thinking much on logic because of time constraint. May be you could've explained more in your steps.
Hi Girish, no offense taken.
I'm not Java coder, so I don't know exactly what your code does.
I'm posting a working C++ code here(with examples)
I don't post code with my answers, because I prefer to leave something to the other person.
#include <iostream>
#include <tr1/unordered_map>
#include <vector>
#include <tr1/memory>
#include <memory>
using namespace std;
using namespace tr1;
int main(){
int i = 0;
string str3 = "gh";
string str1 = "asdfgjkl";
string str2 = "zzyadl";
string s; string s_final; //s_final stores final result
char c;
/*
=========== Remove S3 from S1 ============
*/
bool a1[256];
i = 0;
for(i=0;i<256;i++)
{
a1[i] = false;
}
i = 0;
for(i=0;i<str3.length();i++)
{
c= str3[i];
a1[c] = true;
}
i = 0;
for(i=0;i<str1.length();i++)
{
c = str1[i];
if (a1[c] != true)
s.append(1, c);
}
cout << s << endl;
/*
============ FIND common in S and S2 ============
*/
bool a2[256];
i = 0;
for(i=0;i<256;i++)
{
a2[i] = false;
}
i = 0;
for(i=0;i<str2.length();i++)
{
c = str2[i];
a2[c] = true;
}
i = 0;
for(i=0;i<s.length();i++)
{
c = s[i];
if (a2[c] == true)
s_final.append(1, c);
}
cout << s_final << endl;
return 0;
}
This problem is ambiguous. I think you meant "substring" instead of "subsequence".
And this problem can be solved in linear time using window sliding technique. First remove characters from s1 those also appear on s3. So s1 is exploded into smaller strings. Now for any of these smaller strings, let's call it s4, keep track of the characters seen so far. For an example, if we need to find the shortest substring from string "abbbcba" that also contains "abc", when we find the second a, we don't need the first a any longer. So using a double ended queue we can solve it in O(N) time and O(N + 26) => O(N) space in worst case.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**This class find smallest subword in a string which contains a specified
* set of characters in any sequence. Also it checks for filter characters.
* @author Kishor Kumar Padhan
*
*/
public class StringSeqFinder {
public static void main(String[] s)
{
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
System.out.println(findSmallestString(str1, str2, str3));
}
private static String findSmallestString(String str1, String str2, String str3) {
List<String> list = new ArrayList<String>();
for(int k=0;k<str1.length();k++) {
StringBuffer sb = new StringBuffer();
StringBuffer sb1 = new StringBuffer();
int noOfCharsFound = 0;
String str4=str1.substring(k,str1.length());
for(int i=0;i<str4.length();i++) {
sb.append(str4.charAt(i));
for(int j=0; j< str2.length(); j++) {
if(str2.charAt(j) == str4.charAt(i)) {
if(sb1.indexOf(String.valueOf(str2.charAt(j)))==-1) {
sb1.append(str2.charAt(j));
noOfCharsFound++;
}
}
}
if(noOfCharsFound == str2.length()) {
list.add(sb.toString());
sb = new StringBuffer();
sb1 = new StringBuffer();
noOfCharsFound = 0;
}
}
}
filterList(list, str3);
String small="Not found";
if(list.size()>0) {
small=list.get(0);
for (String string : list) {
if(small.length()>string.length()) {
small=string;
}
}
}
return small;
}
private static void filterList(List<String> list, String str3) {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
if(doesStringContainInvalidCharacter(string,str3)) {
iterator.remove();
}
}
}
private static boolean doesStringContainInvalidCharacter(String string, String str3) {
for (int i = 0; i < str3.length(); i++) {
if(string.contains(String.valueOf(str3.charAt(i)))) {
return true;
}
}
return false;
}
}
Here is my 2 cents to this problem. I guess, i have reduced the iterations significantly. I have not fully tested it. But, hopes this works fine.
package in.co.collection;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
public class MyDemoQuestion {
String str1, str2, str3;
ArrayList<Integer> firstIndexOf = new ArrayList<Integer>();
ArrayList<String> foundList = new ArrayList<String>();
char[] str_2;
char[] str_3;
public MyDemoQuestion(String s1, String s2, String s3) {
str1 = s1;
str2 = s2;
str3 = s3;
str_2 = str2.toCharArray();
str_3 = str3.toCharArray();
}
@SuppressWarnings("unchecked")
boolean find() {
firstIndexOf.clear();
for (int i = 0; i < str_2.length; i++) {
int index = str1.indexOf(str_2[i]);
if (index != -1) {
firstIndexOf.add(index);
}
}
if (firstIndexOf.size() != str2.length()) {
return false;
} else {
Collections.sort(firstIndexOf);
String temp = str1;
System.out.println("Str1 --->"+temp + "--->Indexes of chars in str2---->" + firstIndexOf);
System.out.println("First sequence ---->"+temp.substring(firstIndexOf.get(0), firstIndexOf
.get(firstIndexOf.size() - 1)
- firstIndexOf.get(0) + 1));
foundList.add(temp.substring(firstIndexOf.get(0), firstIndexOf
.get(firstIndexOf.size() - 1)
- firstIndexOf.get(0) + 1));
str1 = str1.substring(firstIndexOf.get(1));
return true;
}
}
void filterList() {
Iterator itr = foundList.iterator();
while(itr.hasNext()){
for (int j = 0; j < str_3.length; j++) {
String x = (String) itr.next();
if (x.contains(String.valueOf(str_3[j]))) {
System.out.println("removed----->"+x);
itr.remove();
break;
}
}
}
}
public static void main(String args[]) {
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
MyDemoQuestion obj = new MyDemoQuestion(str1, str2, str3);
while (obj.find()) {
}
obj.filterList();
System.out.println("------" + obj.foundList);
String shortest = obj.foundList.get(0);
for (String a : obj.foundList) {
if (a.length() < shortest.length()) {
shortest = a;
}
}
System.out.println(shortest);
}
}
public class ThreeStringProblem {
public static void main(String[] args) {
String one = "spqrstrupvqw";
String two = "sprt";
String three = "q";
int minLength = Integer.MAX_VALUE;
String minLengthString = "";
// Sliding window; Start from index 0 with a window of size equivalent
// to String two and increment by one character every iteration
for (int i = 0; i < one.length(); i++) {
for (int j = i + two.length(); j <= one.length(); j++) {
// Get the subString
String subString = one.substring(i, j);
// Check if all the characters match
if (checkIfAllCharactersArePresent(subString, two, three)) {
if (subString.length() < minLength) {
minLength = subString.length();
minLengthString = subString;
}
}
}
}
System.out.println(minLengthString);
}
/**
* The method is used to check if all the characters of String two are
* present in String one but not that of String three
*
* @param first
* @param two
* @param three
* @return
*/
private static boolean checkIfAllCharactersArePresent(String first,
String two, String three) {
boolean result = true;
BitSet bitSet = new BitSet();
// Set first String
for (int i = 0; i < first.length(); i++) {
bitSet.set(first.charAt(i));
}
// Third
for (int i = 0; i < three.length(); i++) {
if (bitSet.get(three.charAt(i))) {
result = false;
return result;
}
}
// Two
for (int i = 0; i < two.length(); i++) {
if (!bitSet.get(two.charAt(i))) {
result = false;
return result;
}
}
return result;
}
}
I liked SumitGaur code. Simple and works well. Here is a verified version of the above code which stops search the substring in str1 if it contains a letter of str3.
package morganstanleyquestions;
import java.util.HashSet;
import java.util.Set;
public class ThreeStringProblem {
public static void main(String args[]){
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
int str2Len = str2.length();
String reqSubString = "";
String minSubSeq = "";
int minSubSeqLength = str1.length();
for(int i=0;i<str1.length();i++){
char startWndChar = str1.charAt(i);
if(str2.indexOf(startWndChar) == -1){
continue;
}
else{
//got the first char in str1 from where to start the window
for(int j = i + str2.length(); j<str1.length(); j++){
reqSubString = str1.substring(i,j);
System.out.println("req sub string to test :" + reqSubString);
int matchCondition = isQualifiedMatch(reqSubString, str2, str3);
if(matchCondition == 1){
if(reqSubString.length()<minSubSeqLength){
minSubSeq = reqSubString;
minSubSeqLength = minSubSeq.length();
}
}
else if(matchCondition == 0){
continue;
}
else{
//match is -1. No need to continue with the window.
break;
}
}
}
}
System.out.println("min sub sequence string :" + minSubSeq);
}
private static int isQualifiedMatch(String subSeq, String str2, String str3){
Set<Character> seqSet = new HashSet<>();
for(int i=0;i<subSeq.length();i++){
seqSet.add(subSeq.charAt(i));
}
for(int i = 0; i<str3.length(); i++){
if(seqSet.contains(str3.charAt(i))) return -1;
}
for(int i = 0; i<str2.length(); i++){
if(!seqSet.contains(str2.charAt(i))) return 0;
}
return 1;
}
}
Here's a brute force method...
/*
* SortString.cc
*
* Created on: Apr 21, 2014
* Author: Tom Tong
*/
#include <iostream>
#include <algorithm>
#include <string>
#include <cstddef>
using namespace std;
int main(int, char**)
{
string s("spqrstrupvqw");
string testFor("sprt");
string avoid("q");
int start = 0;
unsigned int valid = 0;
for(int i = 0; i < s.length(); i++)
{
// lets see how far we can get before hitting the first char of avoid
if (avoid.find_first_of(s[i]) != string::npos) // then char is in the avoid list
{
start = i+1;
valid = 0;
}
else
{
valid++;
}
if (valid >= testFor.length()) // we have valid length
{
string sub = s.substr(start, valid);
//cout << "got substr:" << sub << endl;
unsigned int j;
for(j = 0; j < testFor.length(); j++)
if (sub.find_first_of(testFor[j]) == string::npos) // then sub didn't have one of char's to test for
break;
if (j == testFor.length()) // then we have all the chars
{
// now trim it from front, since the last one added did the trick
std::size_t matches;
do {
if ( (matches = testFor.find_first_of(sub[0])) != string::npos)
sub = sub.substr(1, sub.length() - 1);
} while (matches == string::npos);
cout << "Found string:" << sub << endl;
return true;
}
}
}
cout << "didn't find the substring" << endl;
return false;
}
I liked SumitGaur code. Simple and works well. Here is a verified version of the above code which stops search the substring in str1 if it contains a letter of str3.
package morganstanleyquestions;
import java.util.HashSet;
import java.util.Set;
public class ThreeStringProblem {
public static void main(String args[]){
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
int str2Len = str2.length();
String reqSubString = "";
String minSubSeq = "";
int minSubSeqLength = str1.length();
for(int i=0;i<str1.length();i++){
char startWndChar = str1.charAt(i);
if(str2.indexOf(startWndChar) == -1){
continue;
}
else{
//got the first char in str1 from where to start the window
for(int j = i + str2.length(); j<str1.length(); j++){
reqSubString = str1.substring(i,j);
System.out.println("req sub string to test :" + reqSubString);
int matchCondition = isQualifiedMatch(reqSubString, str2, str3);
if(matchCondition == 1){
if(reqSubString.length()<minSubSeqLength){
minSubSeq = reqSubString;
minSubSeqLength = minSubSeq.length();
}
}
else if(matchCondition == 0){
continue;
}
else{
//match is -1. No need to continue with the window.
break;
}
}
}
}
System.out.println("min sub sequence string :" + minSubSeq);
}
private static int isQualifiedMatch(String subSeq, String str2, String str3){
Set<Character> seqSet = new HashSet<>();
for(int i=0;i<subSeq.length();i++){
seqSet.add(subSeq.charAt(i));
}
for(int i = 0; i<str3.length(); i++){
if(seqSet.contains(str3.charAt(i))) return -1;
}
for(int i = 0; i<str2.length(); i++){
if(!seqSet.contains(str2.charAt(i))) return 0;
}
return 1;
}
}
I liked Sumit Gaur's code.
It is simple and elegant.
I tried my hand on this problem.
Following is the code
package com.javafries.string;
import java.util.ArrayList;
import java.util.List;
/**
* @author vishal.naik
* java-fries.com
*/
public class SmallestStrFinderProblem {
public static void main(String[] args) {
long start = System.currentTimeMillis();
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
findSmallestSubString(str1, str2, str3);
System.out.println("Time taken: "
+ (System.currentTimeMillis() - start));
}
/**
* Finds the smallest substring in str1 which contains all the characters in
* str2 (in any order) and not those in str3.
*
* @param str1 , not null
* @param str2 , not null
* @param str3 , not null
*/
private static void findSmallestSubString(String str1, String str2,
String str3) {
char[] str3Chars = str3.toCharArray();
List<String> possibleSearchStrs = findPossibleSearchStrings(str1, str2,
str3Chars);
int minLength = Integer.MAX_VALUE;
String minStr = "";
for (String word : possibleSearchStrs) {
char[] wordChars = word.toCharArray();
// Iterate over characters of word.
for (int i = 0; i < wordChars.length; i++) {
// Create substring of word starting at current character to str2.length,
// Increment substring's length by one, on every iteration.
for (int j = i + str2.length(); j < wordChars.length; j++) {
String subStr = word.substring(i, j);
if (containsString2(subStr, str2)) {
if (j - i < minLength) {
minLength = j - i;
minStr = subStr;
}
}
}
}
}
if (minStr.isEmpty()) {
System.out.println("No Solution found.");
} else {
System.out.println(minStr);
}
}
/**
* Finds all possible search strings
*
* @param str1 , not null
* @param str2 , not null
* @param str3Chars , not null
* @return
*/
private static List<String> findPossibleSearchStrings(String str1,
String str2, char[] str3Chars) {
List<String> possibleSearchStrs = new ArrayList<String>();
possibleSearchStrs.add(str1);
for (int i = 0; i < str3Chars.length; i++) {
List<String> tempStore = new ArrayList<String>();
for (String word : possibleSearchStrs) {
String[] wordSplit = word.split(String.valueOf(str3Chars[i]));
for (int j = 0; j < wordSplit.length; j++) {
if (wordSplit[j].length() >= str2.length()) {
tempStore.add(wordSplit[j]);
}
}
}
possibleSearchStrs.clear();
possibleSearchStrs.addAll(tempStore);
}
return possibleSearchStrs;
}
/**
* Checks if str2 is contained in subStr.
*
* @param subStr , not null
* @param str2 , not null
* @return
*/
private static boolean containsString2(String subStr, String str2) {
char[] str2Chars = str2.toCharArray();
for (int i = 0; i < str2Chars.length; i++) {
if (!subStr.contains(String.valueOf(str2Chars[i]))) {
return false;
}
}
return true;
}
}
I guess most of you guys are splitting and solving this puzzle which is completely trash way to solve it..
rather just create an array of characters b[26] = count for string s2, c[26] = count for string s3;
now iterate over s1 and whenever you encounter a character of string s3 flush out a[26]; or else keep incrementing the character index in a[26], if a[26] >= b[26] element wise add up all the count in a[26] and thats one possible solution then delete the earliest char in a[26] till it keep satisying a[26]>=b[26] and updating the minimum solution, no other substring memories no splitting nothin, its a basic one pass linear algorithm
public class testing
{
// a="spqrstrupvqw"
// b="sprt"
// c="q"
public static String findSubSequence(String a,String b,String c,ArrayList<String> strSubseq)
{
String result = "";
char[] a1 = new char[a.length()];
char[] b1 = new char[b.length()];
char[] c1 = new char[c.length()];
//ArrayList<String> strSubseq = new ArrayList<String>();
//int[] arrIdx = new int[b.length()];
ArrayList<Integer> arrIdx = new ArrayList<Integer>();
a1 = a.toCharArray();
b1 = b.toCharArray();
c1 = c.toCharArray();
int index,idxExist;
int counter=0;
int minIdx, maxIdx;
String strSub, strSub2;
arrIdx = findSubseqIdx(a1,b1); // find min and max index from a1 for match
if (arrIdx.size()<b.length())
{
if (strSubseq.size() > 0)
{
result = showSubString(strSubseq);
}
else
{
result = "";
}
}
else
{
minIdx = findMin(arrIdx);
maxIdx = findMax(arrIdx);
idxExist = checkIfCharExists(a1,c1[0],minIdx,maxIdx); // check if "q" exists between min and max index
if (idxExist != -1)
{
strSub = a.substring(idxExist+1,a.length());
findSubSequence(strSub,b,c,strSubseq);
}
else
{
strSubseq.add(a.substring(minIdx,maxIdx+1));
for (int k = minIdx+1; k<a.length();k++)
{
findSubSequence(a.substring(k,a.length()),b,c,strSubseq);
}
}
result = showSubString(strSubseq);
}
return result;
}
public static int findChar(char[] seq,char a)
{
int idx = 100;
for (int j=0; j<seq.length; j++)
{
if (a == seq[j])
{
idx=j;
break;
}
}
return idx;
}
public static int findMin(ArrayList<Integer>a)
{
int temp = a.get(0);
for (int i=0; i<a.size(); i++)
{
if (a.get(i)<temp)
{
temp = a.get(i);
}
}
return temp;
}
public static int findMax(ArrayList<Integer>a)
{
int temp = a.get(0);
for (int i=0; i<a.size(); i++)
{
if (a.get(i)>temp)
{
temp = a.get(i);
}
}
return temp;
}
public static int checkIfCharExists(char[] strArray, char c,int minIdx, int maxIdx)
{
int idx = -1;
//char[] strArray = new char[str.length()];
for (int i=minIdx; i<maxIdx; i++)
{
if (strArray[i] == c)
{
idx = i;
break;
}
}
return idx;
}
public static ArrayList<Integer> findSubseqIdx(char[] a1, char[] b1)
{
int index;
ArrayList<Integer> arrIdx = new ArrayList<Integer>();
for(int i=0; i<b1.length; i++)
{
index = findChar(a1,b1[i]);
if (index!=100)
{
arrIdx.add(index);
}
}
return arrIdx;
}
public static String showSubString(ArrayList<String> a)
{
String out = a.get(0);
for (int i=0; i<a.size(); i++)
{
if(a.get(i).length() < out.length())
{
out = a.get(i);
}
}
return out;
}
public static void main (String[] args)
{
//System.out.println("hello world");
String a,b,c,result;
ArrayList<String> strArr = new ArrayList<String>();
/*a = "spqrstrupvqw";
b = "sprt";
c = "q";*/
a = "abdecfgdacdc";
b = "dc";
c = "e";
result = findSubSequence(a,b,c,strArr);
System.out.println(result);
}
}
1. For every character in str1, check if its there in str2
2. Add the character to linkedlist. Before adding check if this character is already there in linkedlist. If its there, then remove that character and add it to the end. In Parallel , update other linked list with its position
3. When size of str1 and linked list are same, find difference between first and last position and compare with old min value
int diff,min=100,first,last,min_first=0,min_last=0;
String str1="spqrstrupvqw ",str2="sprt";
LinkedList<Character> str=new LinkedList<Character>();
LinkedList<Integer> num=new LinkedList<Integer>();
for (int i = 0; i < str1.length(); i++) {
char ch = str1.charAt(i);
if (str2.indexOf(ch) >= 0) {
if (str.contains(ch)) {
int pos = str.indexOf(ch);
str.remove(pos);
num.remove(pos);
}
str.add(ch);
num.add(i);
if (str.size() == str2.length()) {
first = num.getFirst();
last = num.getLast();
diff = last - first;
if (diff <= min) {
min = diff;
min_first = first;
min_last = last;
}
}
}
}
System.out.println(str1.substring(min_first, min_last + 1));
public class FindSubStringinAnotherStringNotInThirdString {
String str1 = null;
String str2 = null;
String str3 = null;
public FindSubStringinAnotherStringNotInThirdString() {
str1 = "spqrstruvpqw";
str2 = "sprt";
str3 = "q";
}
String findSubString() {
String newString = "";
String strArray[] = str1.split(str3);
for (String str : strArray) {
if (str.length() >= str2.length())
newString = str;
// System.out.println(str);
}
return findpositions(newString);
}
public String findpositions(String newString) {
int pos1 = 0, pos2 = 0;
char ch[] = str2.toCharArray();
int a1 = 0, b = 0, c = 1;
for (char a2 : ch) {
a1 = newString.indexOf(a2);
if (a1 > b)
b = a1;
if (a1 < c)
c = a1;
}
// System.out.println(c + " "+b+""+newString.substring(c+1,b+1));
return newString.substring(c + 1, b + 1);
}
public static void main(String[] args) {
FindSubStringinAnotherStringNotInThirdString fs = new FindSubStringinAnotherStringNotInThirdString();
System.out.println("subString is=" + fs.findSubString());
}
}
private static void findSubstring(){
String str1 = "spqrstrupvqw";
String str2 = "sprt";
String str3 = "q";
int startIndex = 0;
int currIndex = 0;
Set set = new HashSet();
while(set.size()<str2.length()){
char c = str1.charAt(currIndex);
if((c+"").equalsIgnoreCase(str3)){
startIndex=++currIndex;
set.clear();
}else if(str2.contains(c+"")){
if((startIndex!=currIndex) && c==str1.charAt(startIndex)){
startIndex++;
currIndex++;
}else{
set.add(c+"");
currIndex++;
}
}else{
currIndex++;
}
}
System.out.println(str1.substring(startIndex, currIndex));
}
}
Requires one pass through str1, so linear time.
1. Find first example from str2 in str1. (Any chars before this must make the string longer and can be ignored.)
2. Iterate through str1, adding characters to candidate_string. If character is in str2 and was not previously in candidate_string, increment match_counter. (This assumes there are no duplicate characters in str2.)
3. If we encounter a character in str3, truncate candidate_string, set match_counter to zero, move iterator to next occurrence of str2 character in str1, then start reading characters into candidate_string again.
4. If length of candidate_string is now >= any previously stored result_string, find the second occurrence of a str2 char in candidate_string (as that's the next possible shortest candidate_string start). Take the substring from that position to the end of candidate_string, decrement match_counter. Continue to iterate through str1 from current position, adding characters to candidate_string.
5. If match_counter == str2.length() then we have matched all candidate chars in a shorter length than the previous result_string. Copy candidate_string to result_string. Take the substring from second occurrence of str2 character in candidate_string to be the new candidate_string, as above.
6. If result_string.length() == str2.length() then this is the shortest possible sequence, so we can break. Otherwise, move the str1 iterator to the next occurrence of str2 in str1, decrement match_counter.
7. Finish when we break on shortest possible sequence or end of str1. Return result_string. Could be empty if there was no substring contained all chars from str2.
Assuming there are only lowercase letters and string 2 has distinct characters.
Time Complexity ~= O (s1.len + s2.len + s3.len)
public String smallest(String s1, String s2, String s3) {
// target string.
char[] c1 = s1.toCharArray();
// allowed characters.
char[] c2 = s2.toCharArray();
//disallowed characters.
char[] c3 = s3.toCharArray();
int[] i2 = new int[26];
int[] i3 = new int[26];
// capturing characters present in string 2.
for (int i = 0; i < c2.length; i++) {
i2[ c2[i] - ‘a’ ] = 1;
}
// same as above for string 3.
for (int i = 0; i < c3.length; i++) {
i3[ c3[i] - ‘a’ ] = 1;
}
// starting & finish of the smallest subsequence.
int s, e;
s = 0;
e = c1.length + 1;
int start, end, count;
start = end = count = 0;
for (int i = 0; i < c1.length; i++) {
// check whether disallowed.
if (i3[ c1[i] - ‘a’ ] == 1) {
// reset all the flags.
start = end = count = 0;
}
// check whether allowed.
else if (i2[ c1[i] - ‘a’ ] == 1) {
start = count > 0 ? start : i;
count++;
// assuming c2 has distinct characters.
if (count == c2.length) {
// found a possible result.
end = i;
// lets see whether this is the smallest.
if ((e-s) > (end - start)) {
e = end;
s = start;
}
// lets starting from next character.
i = start;
start = end = count = 0;
}
}
else {
count = count > 0 ? count+1 : count;
}
}
// check whether we found any subsequence or not.
if (e == (c1.length+1))
return null;
int offset = e - s + 1;
return new String(c1, s, offset);
}
Assuming there are only lowercase letters and string 2 has distinct characters.
Time Complexity ~= O (s1.len + s2.len + s3.len)
public String smallest(String s1, String s2, String s3) {
// target string.
char[] c1 = s1.toCharArray();
// allowed characters.
char[] c2 = s2.toCharArray();
//disallowed characters.
char[] c3 = s3.toCharArray();
int[] i2 = new int[26];
int[] i3 = new int[26];
// capturing characters present in string 2.
for (int i = 0; i < c2.length; i++) {
i2[ c2[i] - ‘a’ ] = 1;
}
// same as above for string 3.
for (int i = 0; i < c3.length; i++) {
i3[ c3[i] - ‘a’ ] = 1;
}
// starting & finish of the smallest subsequence.
int s, e;
s = 0;
e = c1.length + 1;
int start, end, count;
start = end = count = 0;
for (int i = 0; i < c1.length; i++) {
// check whether disallowed.
if (i3[ c1[i] - ‘a’ ] == 1) {
// reset all the flags.
start = end = count = 0;
}
// check whether allowed.
else if (i2[ c1[i] - ‘a’ ] == 1) {
start = count > 0 ? start : i;
count++;
// assuming c2 has distinct characters.
if (count == c2.length) {
// found a possible result.
end = i;
// lets see whether this is the smallest.
if ((e-s) > (end - start)) {
e = end;
s = start;
}
// lets starting from next character.
i = start;
start = end = count = 0;
}
}
else {
count = count > 0 ? count+1 : count;
}
}
// check whether we found any subsequence or not.
if (e == (c1.length+1))
return null;
int offset = e - s + 1;
return new String(c1, s, offset);
}
Below code will solve the problem and this in liner order
package randomProblem;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PatternSearching {
public static Map<String,Integer> mapData = new HashMap<String, Integer>();
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input=br.readLine();
char[] patternToMatch=br.readLine().toCharArray();
String ignore=br.readLine();
List<String> containsPattern=new ArrayList<String>();
String[] convertedString = input.split(ignore);
for(String pattern:convertedString){
if(pattern.length()< patternToMatch.length){
continue;
}
for (int jj = 0; jj < pattern.length() - patternToMatch.length; jj++) {
int offset = 0;
boolean notFound = true;
while (notFound) {
String subString = pattern.substring(jj,
patternToMatch.length + offset);
if (checkIfPatterExist(subString, patternToMatch)) {
containsPattern.add(subString);
notFound = false;
} else {
offset++;
if (!(pattern.length() > patternToMatch.length + offset)) {
break;
}
}
}
}
}
int minLength=containsPattern.get(0).length();
String str=containsPattern.get(0);
for(String value:containsPattern){
if(value.length() < minLength){
minLength=value.length();
str=value;
}
}
System.out.println(str);
}
private static boolean checkIfPatterExist(String pattern, char[] patternToMatch) {
for(int i=0;i<patternToMatch.length;i++){
if(pattern.indexOf(patternToMatch[i])==-1){
return false;
}
}
return true;
}
}
static void Main(string[] args)
{
var str1 = "spqrstrupvqw";
var str2 = "sprt";
var str3 = "q";
var testDictionary = new List<KeyValuePair<string, bool>>();
var str1Split = str1.Split(str3.ToCharArray());
var str2Split = str2.ToCharArray();
foreach (var item in str1Split)
{
var counter = 0;
foreach (var item2 in str2Split)
{
if (item.Contains(item2))
{
counter++;
}
}
if (counter >= str2Split.Length)
{
testDictionary.Add(new KeyValuePair<string, bool>(item, true));
}
}
var fnalResult = testDictionary.Select(x =>
{
var myDict = new Dictionary<char, int>();
var result = "";
foreach (var item in testDictionary)
{
if (item.Key.Length <= x.Key.Length)
{
result = x.Key;
}
}
if (!string.IsNullOrWhiteSpace(result))
{
var index = 0;
foreach (var item in result.ToCharArray())
{
if (str2.Contains(item))
{
if (myDict.ContainsKey(item))
{
myDict[item] = index;
}
else
{
myDict.Add(item, index);
}
}
index++;
}
}
var min = myDict.OrderBy(p => p.Value).FirstOrDefault().Value;
var max = myDict.OrderBy(p => p.Value).LastOrDefault().Value;
return result.Substring(min, max);
}).Where(x => x != null).FirstOrDefault();
Console.WriteLine(fnalResult);
}
public static void main(String[] args) {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
for (String s4 : s1.split(s3)) {
if (s4.length() >= s2.length()) {
getComb(s4, s2);
}
}
}
public static boolean checkString(String sData, String sCheck) {
for (char c : sCheck.toCharArray()) {
if (!sData.contains(Character.toString(c))) {
return false;
}
}
return true;
}
public static void getComb(String sData, String sCheck) {
String sComb;
aa: for (int j = sCheck.length() - 1; j < sData.length(); j++) {
for (int i = 0; i < sData.length() - j; i++) {
sComb = sData.substring(i, i + j + 1);
if (checkString(sComb, sCheck)) {
System.out.println(sComb);
break aa;
}
}
}
}
public class interview {
public static void main(String[] args) {
String s1 = "spqrstrupvqw";
String s2 = "sprt";
String s3 = "q";
for (String s4 : s1.split(s3)) {
if (s4.length() >= s2.length()) {
getComb(s4, s2);
}
}
}
public static boolean checkString(String sData, String sCheck) {
for (char c : sCheck.toCharArray()) {
if (!sData.contains(Character.toString(c))) {
return false;
}
}
return true;
}
public static void getComb(String sData, String sCheck) {
String sComb;
aa: for (int j = sCheck.length() - 1; j < sData.length(); j++) {
for (int i = 0; i < sData.length() - j; i++) {
sComb = sData.substring(i, i + j + 1);
if (checkString(sComb, sCheck)) {
System.out.println(sComb);
break aa;
}
}
}
}
}
1. Split the str1 with each character of the str3.
- Kishore April 21, 20142. Now iterate all the words and check the constraint that word contain all the characters of str2, Checking can be skipped by comparing string lengths.
3. Return the minimum length string which satisfies point 2.