How to find smallest substring which contains all characters from a given string?

Posted by Rajendra on Stack Overflow See other posts from Stack Overflow or by Rajendra
Published on 2010-03-17T03:00:38Z Indexed on 2010/03/17 3:01 UTC
Read the original article Hit count: 209

Filed under:

string-manipulation

|

interview-questions

I have recently come across an interesting question on strings. Suppose you are given following:

Input string1: "this is a test string"
Input string2: "tist"
Output string: "t stri"

So, given above, how can I approach towards finding smallest substring of string1 that contains all the characters from string 2?

© Stack Overflow or respective owner

Related posts about string-manipulation

String manipulation in C#

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the following text, I need to extract the exception name and the continuing sentence from the file, but the file has continuous sentences without a space. ??????>????????????????????????????????????????????????????????????????????????????????????????????????????????????????? ??????????… >>> More
Regarding String manipulation

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a String str which can have list of values like below. I want the first letter in the string to be uppercase and if underscore appears in the string then i need to remove it and need to make the letter after it as upper case. The rest all letter i want it to be lower case. "" "abc" "abc_def" "Abc_def_Ghi12_abd" "abc__de" "_" Output: "" "Abc" "AbcDef" "AbcDefGhi12Abd" "AbcDe" "… >>> More
String manipulation in C# ( Brainstroming ;-) )

as seen on Stack Overflow - Search for 'Stack Overflow'
I have the following text , i need to extract the exception name and the continuing sentence from the file... but the file has continues sentence without a space. ?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????… >>> More
php string-manipulation (clear the "_" and the timestamp)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi! I cant find the way how to strip the useless section of my string (read from SQL) I've tried the strreplace and truncate but those was not good at all. I've got a string variable called $stuff if $stuff = 145_timestamp i want to clear the _ and the chars after it. so i want to $stuff be 145… >>> More
c# string manipulation

as seen on Stack Overflow - Search for 'Stack Overflow'
i have string of 9 letters. string myString = "123987898"; I want to retrieve frist 3 letter "123" then 2 more leters "98" and then 4 more letters "7898". Which c# string function support this functionality. >>> More

Related posts about interview-questions

SQL SERVER – Interview Questions & Answers Needs Your Help

as seen on SQL Authority - Search for 'SQL Authority'
About an year ago, I had posted SQL Server related Interview Questions and Answers. It was very well received in community. I have received many comments, suggestions and emails on this subject. I am planning to upgrade the Interview Questions and Answers and take it to next level. Here, I need your… >>> More
SQL SERVER – Interview Questions and Answers – Frequently Asked Questions – Introduction – Day 1 of 31

as seen on SQL Authority - Search for 'SQL Authority'
List of all the Interview Questions and Answers Series blogs Posts covering interview questions and answers always make for interesting reading. Some people like the subject for their helpful hints and thought provoking subject, and others dislike these posts because they feel it is nothing more… >>> More
C# Multithreading Interview questions for a senior developer/designer position.

as seen on Programmers - Search for 'Programmers'
I know there have been a great deal of interview questions posted on SO and specifically i like the post "Good C# interview questions for a Senior developer position" But i really wondered what sort of interview questions were asked to a senior developer or technical consultant on multithreading… >>> More
SharePoint interview questions

as seen on Stack Overflow - Search for 'Stack Overflow'
Let's have a list of some good interview questions for SharePoint developers. Please provide one question per entry, and if possible, the answers. Also, please feel free to suggest corrections if the provided answers are wrong. I will go first: Q: How does SharePoint store pages? A: How-to-locate-sharepoint-document-library-source-page-on-the-server… >>> More
MySQL Interview Questions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I've been asked to screen some candidates for a MySQL DBA / Developer position for a role that requires an enterprise level skill set. I myself am a SQL Server person so I know what I would be looking for from that point of view with regards to scalability / design etc but is there anything… >>> More