1.最长子字符串
题目为：
【题目】
给定一个字符串，给定一个数字k ( 0< k ≤ 字符串长度)，输出最长的包含k个不同字符子串的长度。
【Example】
“cbca”, k=2，输出最长的包含2个不同字符子串的长度。
答案：3
最容易想到的是暴力解法，就是遍历求出字符串的所有子串，并找出不同字符为k的最长字符，Python代码如下：
def find_max_substring(string, k): str_length = len(string) sub_string_list = (string[i:i + j + 1] for j in range(str_length) for i in range(str_length - j)) length_list = [] for sub_string in sub_string_list: if len(set(list(sub_string))) == k: length_list.append(len(sub_string)) return max(length_list) if __name__ == '__main__': string = input() k = int(input()) max_length = find_max_substring(string, k) print(max_length)
显然，这种实现方式效率是很低的，虽然使用了生成器，但是在性能方面还是有很大的问题，同时未考虑特殊情况。
后来查询了一些资料，使用了同向双指针和字典来对实现方式进行了优化：
def find_max_substring(string, k): str_length = len(string) if str_length == 0 or k == 0: return 0 count = 0 left = 0 right = 0 res = 0 count_dic = {} while right < str_length: if string[right] not in count_dic or count_dic[string[right]] == 0: count += 1 count_dic[string[right]] = 1 else: count_dic[string[right]] += 1 right += 1 while count > k: count_dic[string[left]] -= 1 if count_dic[string[left]] == 0: count -= 1 left += 1 res = max(res, right - left) return res if __name__ == '__main__': string = input() k = int(input()) max_length = find_max_substring(string, k) print(max_length)
在字符串长度为0或者k为0时直接返回0；
通过使用同向双指针的方式，可以做到只遍历一次字符串就能得到答案，从而使时间复杂度为O(n)，在字符串上移动滑动窗口的两个指针，来保证窗口内的字符不超过k个，具体如下：
- 设置指针left、right初始位置均为0，初始化计数数组；
- 当right小于字符串长度时，每次判断字符s[right]是否位于计数数组中，不在则计数count加1，同时对字典进行更新，并使right指针向右移动；
- 在字符数超过k时，需要移去窗口中最左侧的字符string[left]，同时向右移动left指针使得滑动窗口只包含k个不同字符；
- 更新最大长度
res = max(res, right - left)。
此时运行结果如下：
可以看到，运行效率还是相对较快的。
可以在https://www.lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/description使用IDE进行运行测试和性能评估。
2.字符串同构
题目为：
【题目】
给定两个字符串s和t，确定它们是否同构。
如果可以替换s中的字符得到t，那么两个字符串是同构的。
在保持字符顺序的同时，必须用另一个字符替换出现的所有字符。两个字符不能映射到同一个字符，但一个字符可以映射到自身。
【Example】
Input: s = “egg”, t = “add”
Output: true
Input: s = “foo”, t = “bar”
Output: false
Input: s = “paper”, t = “title”
Output: true
可以看到，实际上就是判断字符串是否结构相同，可以按照如下思路实现：
两个字符串对应位置上的字母要具有一一对应的关系，如果s[i]为a、t[i]=b，则a对应的就是b，如果后面s[j]为a，则t[j]也必须为b，若t[j]为其他字母，则判定为非同构。
要实现这种一一对应关系，可以使用字典，具体如下：
如果两个字符串长度不同，直接返回False；
如果字典中没有相应成对字母，就在字典中加入字母对；
如果键已经存在，判断一下t中对应的字母是否和字典中对应的值相同，不相同则肯定是非同形态，相同则继续循环；
如果s中不同的字母，对应了t中相同的值，即不同的键对应的值相同，例如s='mn'、t=‘mm’，这是属于非同构的，可以通过判断键、值的唯一值个数来判断是否属于这种情况。
Python代码实现如下：
def is_isomorphic(s, t): s_len = len(s) if s_len != len(t): return False char_pair = {} for i in range(s_len): if s[i] not in char_pair: char_pair[s[i]] = t[i] elif char_pair[s[i]] != t[i]: return False return len(char_pair) == len(set(char_pair.values())) if __name__ == '__main__': s = 'egg' t = 'add' res = is_isomorphic(s, t) print(res)
示例输出：
True
LeetCode测试结果如下：
