【LeetCode】Longest Substring Without Repeating Characters

题目描述

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

问题分析

这个题寻找最长的不重复字串，即在一个字符串里面，所有的字符都没有出现，可以定义个表，用来记录每一个字符第一次出现的位置，当发现有位置已经有字符了，将下表移动到index+1的位置，同时不断记录最长字串长度。

代码

public class Solution {
   public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int res = 1;
        boolean[] exist = new boolean[256];
        int start = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (exist[ch]) {
                res = Math.max(res, i - start);
                for (int k = start; k < i; k++) {
                    if (s.charAt(k) == ch) {
                        start = k + 1;
                        break;
                    }
                    exist[s.charAt(k)] = false;
                }
            } else
                exist[ch] = true;
        }
        res = Math.max(res, s.length() - start);
        return res;

    }
}

总结

这个题并不算难，理解意思就会有思路的，只要能想到定义字符表基本上就能做出来

个人声明

本文章均为原创，转载请说明出处，谢谢
个人说明

本人对编程有很大兴趣，希望跟大家一起交流
欢迎访问个人论坛：www.dabenmo.com
如有任何问题请邮件：jianxiawzx@126.com