求修复最长无重复字符子串长度计算程序，输入'dvdf'返回错误值

你的程序在输入字符串"dvdf"时返回4（错误结果），正确结果应为3，问题出在重复字符的判断条件上。

错误原因 #

原代码中判断重复字符的条件是：

if (positions[curchar] != -1 && positions[curchar] > startpos)

当重复字符的历史位置等于当前子串的起始位置（startpos）时，这个条件不会触发，导致startpos没有及时移动，最终计算的长度包含了重复字符。

以"dvdf"为例：

1. 处理索引2的字符'd'时，它的历史位置是0，和当前startpos（0）相等，此时本应将startpos移动到1，但原条件不满足，导致后续计算整个字符串长度时，错误地从0开始算到末尾，得到4。

修复后的代码 #

将判断条件中的>改为>=即可：

#include <stdio.h>
int lengthOfLongestSubstring(char *);

int main(void) {
  char *str = "dvdf";
  int result = lengthOfLongestSubstring(str);
  printf("%d", result);

  return 0;
}

int lengthOfLongestSubstring(char *s){
    int startpos = 0, curposition = 0, maxlen = 0;
    int positions[256];

    for (int i = 0; i < 256; i++)
    {
        positions[i] = -1;
    }

    while (s[curposition] != '\0') {
        char curchar = s[curposition];
        // 修改此处的判断条件，将 > 改为 >=
        if (positions[curchar] != -1 && positions[curchar] >= startpos) {
          int len = curposition - startpos;
          if (len > maxlen) maxlen = len;
          startpos = positions[curchar] + 1;
        }

        positions[curchar] = curposition;
        curposition++;
    }
    int len = curposition - startpos;
    if (len > maxlen) maxlen = len;
    return maxlen;
}

验证结果 #

修复后运行程序，输入"dvdf"会输出正确结果3，对应最长无重复子串"vdf"。

内容的提问来源于stack exchange，提问作者Yasen Tsvetkov