二分查找求解最长无重复子串时的错误排查

问题背景 #

给定字符串s，找出最长无重复字符子串的长度。示例输入s="pwwkew"，输出3（对应子串"wke"）。以下是实现代码，但在该测试用例上出现WA：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size() ;
        vector<char> s1 ;
        int maxi = 0 ;
        
        for(int i = 0;i<n;i++){
            if(binary_search(s1.begin(),s1.end(),s[i])){
                s1.clear();
            }
            
            s1.push_back(s[i]);
            int p = s1.size() ;
            maxi = max(maxi , p) ;
            
        }
        return maxi ;
        
    }
};

错误点分析 #

• binary_search使用前提错误：binary_search函数要求容器内元素必须是已排序状态，否则查找结果是未定义的。你的vector<char> s1是按字符在原字符串中的出现顺序插入的，并非有序结构。比如当s1为[w,k,e]时，字符的ASCII码顺序是e < k < w，但s1内是逆序存储，binary_search无法在这种无序容器中正确定位到已存在的w，导致重复字符被误判为不存在，进而出现[w,k,e,w]这种包含重复字符的错误情况。
• 重复字符处理逻辑错误：即使binary_search能正确找到重复字符，直接清空整个s1的做法也不合理。遇到重复字符时，正确逻辑应该是移除重复字符及其之前的所有元素，保留重复字符之后的有效子串再添加当前字符，而不是直接清空容器，这会丢失原本可以保留的有效子串，导致无法统计到最长的无重复子串。

内容的提问来源于stack exchange，提问作者Avik Pathak