算法：字符串和二分搜索相关题目

字符串面试的概念
回文、
子串（连续）、子序列（不连续）
前缀树（Trie树）、后缀树和后缀数组
匹配
字典序

字符串题目类型
1 规则判断
判断字符串是否符合整数、浮点数
是否返回回文规则
2 数字运算
大整数相关的加、减、乘、除 操作
3 与数组操作有关 排序技巧、快排划分技巧

最长回文子串 manachar算法 马拉车算法
kmp 解决字符串匹配问题
前缀树、后缀树、后缀数组 问题 – 通常面试极少出现

1. 给定彼此独立的两棵树头节点分别为t1和t2，判断t1中是否有与t2树拓扑结构完全相同的子树。
   （判断t2是否是t1的子树？）
   常规解法：二叉树遍历 + 匹配问题 O(N*M) leetcode 572 树的子树
   最优解: 二叉树序列化 + KMP算法 O(N+M)

2. 给定两个字符串 str1 和 str2 ，判断两个字符串是否互为变形词。
   https://leetcode.cn/problems/dKk3P7/
   哈希表统计词频 C++ 固定大小数组统计词频

3. 给定两个字符串，判断这两个字符串是否互为旋转词。
   str1和str2，str1+str1 其实穷举了所有旋转过程，然后使用kmp算法判断str2是否为str1的子串
   https://www.nowcoder.com/questionTerminal/687deda2cc57473499e058207f6258cf

4. 给定一个字符串，在单词间做逆序调整。
   https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/

5. 给定一个字符串str，以及整数i，请将str[0:i]移到右侧，str[i+1…N-1]移到左侧。要求时间复杂度O(N)，空间复杂度O(1)。
   做三次逆序变换。

6. 给定一个字符串string，将其中所有空格字符替换成"%20"，假设str后有足够的空间
   lc:https://leetcode.cn/problems/ti-huan-kong-ge-lcof/
   nowcoder: 剑指offer 替换空格

7. 给定一个字符串string，判断是不是整体有效的括号字符串。
   只需要维护一个统计变量，计算右括号与左括号数量的差值。

8. 给定一个字符串string，返回最长无重复字符串子串的长度。
   最优：时间复杂度O（n），额外空间复杂度 O（n）
   双指针：时间复杂度 O(n)，额外空间复杂度 O(字符串长度)
   lc第3题：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        start = 0
        end = 1
        dic = {s[0]:0}
        n = len(s)
        length = 1
        while end < n:
            if s[end] not in dic:
                dic[s[end]] = end
                length = max(length, end-start+1)
            else:
                last = dic[s[end]]
                start = max(last+1, start)
                length = max(length, end-start+1)
                dic[s[end]] = end
            end += 1
        return length