如何编写接受字符串并返回最长有效子字符串的方法

Question

我一直在和一个朋友练习面试问题，他把他编的这道题扔给我：

给定一个方法来告诉您一个字符串是否有效，请编写一个方法来获取一个字符串，并返回最长的有效子字符串（而不对字符重新排序）。

>

检查输入字符串

检查inputstring的所有子集，使用length==inputstring length-1

以此类推，直到检查所有长度为1的子集，然后返回false

但不幸的是，我很难理解。

最好的解决方案是在所有子集中进行深度优先的递归迭代，并从那里返回最长的有效字符串吗？

Answer 1

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

这将为给定输入生成所有可能的子字符串(中的)，并返回第一个/最长的有效子字符串。