阴沟翻船题——Longest Substring Without Repeating Characters

一、事件概述

今天接到一个面试，让线上做题。面试官出了个leetcode的题。题目如图所示：

我没有刷过leetcode，上学时候我们做的hdu-acm和codeforces。咋一接到题目，看到是个字符串题，并且找最长字串，第一反应就是DP。
这一反应，导致我始终无法绕靠DP找迭代的思路，最后没做出来。
后来静下心来一想，这TM就是道水题。

二、题解思路

2.1 题目大意

给一个字符串，找到一个最长的自串，使这个子串没有重复的字符。

2.2 方案1——2重循环求解

由于assic码字符范围只有0~255，那么我们可以用一个bool[] 数组，记录特定字符是否已经使用过。
每重循环，查找以i开头的字符串，最长走到哪里没有重复字符。

int Solution3::lengthOfLongestSubstring(std::string s)
{int maxLen = 0;for (int i = 0; i < s.size(); i++) {bool arr[256];memset(arr, 0, sizeof(bool) * 256);int curLen = 0;for (int j = i; j < s.size(); j++) {char c = s[j];if (!arr[c]) {arr[c] = true;curLen++;}else {break;}}maxLen = max(maxLen, curLen);}return maxLen;
}

2.3 方案2——一次循环模拟

2.2是个O(n^2)的算法，我们能否优化以下么？
以abcabcabdd为例子，我们只看i=0时的循环，当i=3时，当前字符为a，在之前出现过了。
我们是否可以再定义一个起始指针beg，当出现重复的字符时，我们把beg指针后移，并且置空beg位置字符的标志位，直到beg处的字符和i处的字符相同。
基于这个想法，就有了这段代码：

int Solution3::lengthOfLongestSubstring_effective(std::string s)
{bool arr[256];memset(arr, 0, sizeof(bool) * 256);int beg = 0, idx = 0;int sizeN = s.size();int maxRes = 0;int curRes = 0;while (idx < sizeN) {char c = s[idx];if (arr[c]){maxRes = max(maxRes, curRes);char bc;do{bc = s[beg];arr[bc] = false;curRes--;beg++;}while (beg < idx && bc != c);}curRes++;arr[c] = true;idx++;}maxRes = max(maxRes,curRes);return maxRes;
}

三、感想

未来我们都会变成招聘的一方，笔试算法题的目的是看候选人的编码能力，我们应当尽量避免误导的情况。尤其是一些问题，看着很像算法题，市面上类似问题都有个巧妙的解法。而候选人不见得是刚从学校出来，可能很多年不碰算法题了。这时这样的问题就会造成很大的困扰。
我认为，如果考察候选人编码模拟能力，最好找些很明确的搜索题，或者一眼看上去就不像搞算法的模拟题。
如果硬要出这道题，可以给出提示，关键词——模拟。给出时间复杂度建议O(n)。我相信这样就可以更客观的评价候选人的编码能力了。