字符串的子串

目录

• 找到字符串的最长无重复字符子串
• 字符串中的第一个唯一字符
• 字符串的字典序最长子序列
• 最小包含子串的长度
• 字符串的全排列（python）

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

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

举例：

str = 'abcd'，返回4.

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

要求：

如果str的长度为N，请实现时间复杂度为O（N）的方法。

思路：时间O（N），空间O（N）

遍历字符串中的每一个元素。借助一个辅助键值对来存储某个元素最后一次出现的下标。用一个整形变量存储当前无重复字符的子串开始的下标。

代码：

def maxUnique(s):
    if s == None or s == '':
        return 0
    dic = {}
    res , start = 0 , -1
    for i in range(len(s)):
        if s[i] in dic:
            start = max(start,dic[s[i]])
        tmp = i - start
        dic[s[i]] = i
        res = max(res,tmp)
    return res
    
s = 'ababcadc'
maxUnique(s)

二、题目：给定一个字符串，输出所有的字典序。

如：

输入字符串：'ac'，输出：['ac','ca']

输入字符串：‘abc' ,输出：['abc','acb','bac','bca','cab','cba']

输入字符串：‘acc'，输出：['acc','cac','cca']

思路：递归

如：'abc'，对于'a'，返回’bc'的全排列字典序，对于'b'，返回'ac'的全排列，对于'c'，返回'ab‘的全排列。【循环加递归】

代码1：

def printstr(s):
    liststr=[]
    result=[]
    if len(s)==1:
        liststr.append(s)
        return liststr
    else:
        for i in range(len(s)):
            liststr1=printstr(s[:i]+s[i+1:])
            for item in liststr1:
                result.append(s[i]+str(item))
        return list(set(result))
s=input()
print(printstr(s))

代码2：

res = list()
def traverse(ss,join_ss=''):
    if ss:
        for i,s in enumerate(ss):
            sub_ss = ss[:i]+ss[i+1:]
            traverse(sub_ss,join_ss+s)
    elif join_ss and join_ss not in res:
        res.append(join_ss)
    return res

result = traverse('abc','')
print(result)