【今晚八点在线讲座】面试真题，理解了答案后保你两眼放光！

明晚八点，牛课堂继续与大家见面！http://www.nowcoder.com/live/11

左老师：明天的题目都是字符串问题，既有算法原型manacher算法，也有一个很不错的贪心策略，而且这几个题的时间复杂度要求都很高，等你理解答案之后保证眼前一亮！

题目一

在字符串的末尾添加字符使得整体都是回文串

【题目】

给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添加的最短字符串。

【举例】

str="12"。在末尾添加"1"之后，str变为"121"，是回文串。在末尾添加"21"之后，str变为"1221"，也是回文串。但"1"是所有添加方案中最短的，所以返回"1"。

【要求】

题目二

找到字符串的最长无重复字符子串

【题目】

给定一个字符串str，返回str的最长无重复字符子串的长度。

【举例】

str="abcd"，返回4

str="aabcb"，最长无重复字符子串为"abc"，返回3。

【要求】

题目三

拼接所有字符串产生字典顺序最小的大字符串

【题目】

给定一个字符串类型的数组strs，请找到一种拼接顺序，使得将所有的字符串拼接起来组成的大字符串是所有可能性中字典顺序最小的，并返回这个大字符串。

【举例】

strs=[ "abc"，"de" ]，可以拼成"abcde"，也可以拼成"deabc"，但前者的字典顺序更小，所以返回"abcde"。

strs=["b"，"ba" ]，可以拼成"bba"，也可以拼成"bab"，但后者的字典顺序更小，所以返回"bab"。

【要求】

题目四

最小包含子串的长度

【题目】

给定字符串str1和str2，求str1的子串中含有str2所有字符的最小子串长度。

【举例】

str1="abcde"，str2="ac"。因为"abc"包含str2的所有字符，并且在满足这一条件的str1的所有子串中，"abc"是最短的，返回3。

str1="12345"，str2="344"。最小包含子串不存在，返回0。

【要求】

如果str1的长度为N，str2的长度为M，请实现时间复杂度O(N)的方法。