查找不重复字符最长子串的长度

一、问题描述

今天和同学在做一道牛客上的笔试算法题目，题目是这样的：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。其中给出了几个示例：

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

二、手工过程

遇到问题首先分析其手工过程，假设原字符串str = "abcabcbb"，思路是这样的，既然是字符串，那必然每个字符的ASIIC码值是一定的，故，构建一个128个元素的数组asiic_arr[128]，用来表示该字符在原字符串中出现的下标，初始化该数组的所有元素为-1，表示目前没有出现过该字符。比如，第一个字符为’a’，则：

asiic_arr['a'] = 0;
asiic_arr['b'] = 1;
asiic_arr['c'] = 2;
...

当遇到了重复的字符’a’时，就该计算当前的子串长度cur_sub_len了，子串长度的计算方法就是用当前下标index减去用来计算子串在原串中的初始下标的sub_start_index，由于sub_start_index初始化为0，表示从原串下标为0的地方开始寻找子串。

计算完成当前的子串长度后，则需要与最大的子串长度max_sub_len做对比，如果cur_sub_len > max_sub_len则应该令max_sub_len = cur_sub_len。

计算完成子串的长度后，就需要继续往下走，这时候就应该从重复的字符的下一个位置来重新计算下一次的子串长度了，也就是需要令sub_start_index为字符’b’的位置，也就是令sub_start_index = asiic_arr['a'] + 1。

之后需要更新asiic_arr['a']的值为当前的下标index，即，asiic_arr[str[index]] = index。

直到遍历完成整个字符串后，还需做最后一次计算子串的操作，并比较max_sub_len的值。

其中最复杂的问题就是如何判断重复的问题，根据推理后的结果表明，重复的认定方法如下：

• 若当前元素在asiic_arr数组中的值不为-1，则，代表该元素曾经在原串str中出现过，就需做进一步的判断。
  • 若该元素在asiic_arr数组中的值小于sub_start_index，则说明子串的计算中已经不再包含这个重复的元素了，可以认为这时候的子串中并不存在重复元素，则应该继续往后寻找，也就是继续执行index++的操作。
  • 若该元素在asiic_arr数组中的值大于等于sub_start_index，则代表子串的计算中已经包含了相同的该字符，则需要进行“重复”的逻辑了。

三、代码思路

根据手工过程的描述，基本已经可以构想出代码的整体框架了，用了C与Java两种方式分别实现：

#include <stdio.h>
#include <string.h>

int lengthOfLongestSubstring(char * str){
  int index = 0;
  int asiic_arr[128];
  int max_sub_len = 0;
  int cur_sub_len = 0;
  int sub_start_index = 0;
  int i = 0;

  for (i = 0; i < sizeof(asiic_arr)/sizeof(int); i++)
  asiic_arr[i] = -1;

  while (index < strlen(str)) {
    if (asiic_arr[str[index]] != -1 && asiic_arr[str[index]] >= sub_start_index) {
      cur_sub_len = index - sub_start_index;//计算子串长度；
      max_sub_len = cur_sub_len > max_sub_len ? cur_sub_len : max_sub_len;//更新最大子串长度
      sub_start_index = asiic_arr[str[index]] + 1;//更新startIndex的值；
    }
    asiic_arr[str[index]] = index;
    index++;//更新ASIIC数组中元素的值；
  }

  cur_sub_len = index - sub_start_index;//计算子串长度；
  max_sub_len = cur_sub_len > max_sub_len ? cur_sub_len : max_sub_len;//更新最大子串长度

  return max_sub_len;
}

int main(void)
{
  char str[80] = {0};

  gets(str);
  printf("%d\n", lengthOfLongestSubstring(str));

  return 0;
}

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() <= 0) return 0;
    if (s.length() == 1) return 1;
    int[] ascii = new int[128];
    //初始化数组为全-1
    initArr(ascii);
    int startIndex = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        if (ascii[s.charAt(i)] != -1) {
            if (ascii[s.charAt(i)] >= startIndex) {
                //计算当前子串的长度
                int len = (i - startIndex);
                if (len > max) max = len;
                //重新记录起始下标
                startIndex = ascii[s.charAt(i)] + 1;
            }
        }
        ascii[s.charAt(i)] = i;
    }
    if (max < (s.length() - startIndex)) max = s.length() - startIndex;
    return max;
}

private void initArr(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = -1;
    }
}

四、clang的坑

在编写c程序的时候，我在本地使用gcc编译的结果完全正确，但是提交到牛客上使用clang编译结果就会出错，折腾了一下午，结果发现是clang编译的问题。具体的坑就在这几行代码：

  while (index < strlen(str)) {
    if (asiic_arr[str[index]] != -1 && asiic_arr[str[index]] >= sub_start_index) {
      cur_sub_len = index - sub_start_index;//计算子串长度；
      max_sub_len = cur_sub_len > max_sub_len ? cur_sub_len : max_sub_len;//更新最大子串长度
      sub_start_index = asiic_arr[str[index]] + 1;//更新startIndex的值；
    }
    asiic_arr[str[index]] = index++;//坑位
    //index++;
  }

原本我为了代码简洁起见将index++写在了坑位处，结果，我通过gcc编译运行完全没有问题的程序在clang的编译下会出现Unsequenced modification and access to ‘index'，该链接里详细描述了在编译代码时clang编译器可能无法准确的识别序点（sequence point），故导致index的访问出现问题，因此应该避免这样书写代码，于是我将index++单独列出一行来，通过clang编译运行完全正确了。

人生处处是坑啊，好好学习，天天向上，欢迎对本文指正批评！