欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3. Longest Substring Without Repeating Characters(无重复字符的最长子串)

程序员文章站 2024-02-26 14:14:10
...

3. Longest Substring Without Repeating Characters(无重复字符的最长子串)

1 问题描述

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

2 C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int begin = 0;
        int result = 0;
        string word = "";
        int word_map[128] = {0};
        for(int i=0; i<s.length(); i++) {
            word_map[s[i]]++;
            if(word_map[s[i]] == 1) {
                word += s[i];
                if(result < word.length())
                    result = word.length();
            }
            else {
                while(begin < i && word_map[s[i]] > 1) {
                    word_map[s[begin]]--;
                    begin++;
                }
                word = "";
                for(int j=begin; j<=i; j++) {
                    word += s[j];
                }
            }
        }
        return result;

    }
};
相关标签: leetcode