CODEWITHSUNDEEP
stringalgorithm
A O
A O

Reputation: 5698

How to write a method that takes a string and returns the longest valid substring

I have been practicing interview questions with a friend, and he threw me this one he made up:

Given a method that tells you if a string is valid, write a method that takes a string, and returns the longest valid substring (without reordering the characters).

My first brute force solution would be to find all of the subsets of the input string, and then plug them through (longest to shortest) the given method till a valid string is found and return that.

But that obviously isn't good enough.

So I was trying to think of it this way:

The problem in my head, then, is that in order for this to be optimal, we want to utilize the fact that we only care for the longest valid string. If I were to check each subset recursively, then I would be doing a depth-first traversal of the subsets, when I'm really looking for a breadth-first, so I can find the longest quicker.

Once I realized that, I got stuck. I couldn't even come up with pseudo code to tackle this problem.

Is a "breadth-first" search of the subsets of a string even possible?

The closest solution I could find was on the math stackexchange, somebody posted a promising looking answer-- https://math.stackexchange.com/questions/89419/algorithm-wanted-enumerate-all-subsets-of-a-set-in-order-of-increasing-sums

but it unfortunately is pretty hard for me to comprehend.

Would the best solution just be a depth-first recursive iteration through all of the subsets and return the longest valid string from there?

Upvotes: 0

Views: 161

Answers (1)

user4668606
user4668606

Reputation: 

string in

for int sub_len in len(in) , 1 //length of the substring must be smaller than/equal to
                               //the length of the input and atleast 1
    for int sub_offset in 0 , len(in) - sub_len
                               //the offset of the string must be in [0 , n]
                               //where n is the number of characters that are not in the
                               //substring
         string sub = substring(in , sub_offset , sub_len)

         if isValid(sub)
              return sub

This generates all possible substrings for a given input (in) and returns the first/longest valid substring.

Upvotes: 1

Related Questions