最长无重复字符的子串 lintcode

痛定思痛。 2022-07-16 09:54 202阅读 0赞

给定一个字符串，请找出其中无重复字符的最长子字符串。

您在真实的面试中是否遇到过这个题？

Yes

样例

例如，在`"abcabcbb"`中，其无重复字符的最长子字符串是`"abc"`，其长度为 `3`。

对于，`"bbbbb"`，其无重复字符的最长子字符串为`"b"`，长度为`1`。

[挑战 ][Link 1]

O(n) 时间

<pre name="code" class="java">public class Solution {
        /**
         * @param s: a string
         * @return: an integer 
         */
        public int lengthOfLongestSubstring(String s) {
            // write your code here
            int res = 0;
            String resStr = "";
            if(s == null || s.length() == 0)return res;
            if(s.length() == 1)return res+1;
            int len = s.length();
            int[] tmp = new int[len];
            Set<Character> set = new HashSet<>();
            res = 1;
            for(int i = 1; i < len; i++){
                if(!set.isEmpty())set.clear();
                int tmpLen = 0;
                for(int j = i; ; j--){
                	if(j < 0){
                        res = Math.max(tmpLen, res);
                        break;
                	}
                    if(!set.contains(s.charAt(j))){
                        set.add(s.charAt(j));
                        tmpLen++;
                    }else{
                        res = Math.max(tmpLen, res);
                        break;
                    }
                }
                
            }
            
            return res;
        }
    }

其他解法参考 [http://blog.csdn.net/luxiaoxun/article/details/8036544][http_blog.csdn.net_luxiaoxun_article_details_8036544]

[Link 1]: http://www.lintcode.com/zh-cn/problem/longest-substring-without-repeating-characters/#challenge
[http_blog.csdn.net_luxiaoxun_article_details_8036544]: http://blog.csdn.net/luxiaoxun/article/details/8036544