Description

Notes

Testcase

Judge

Given a string s, find the length of the longest substring T that contains at most k distinct characters.

Have you met this question in a real interview? Yes

Example

For example, Given s = "eceba", k = 3,

T is "eceb" which its length is 4.

Challenge

O(n), n is the size of the string s.

Tags

LintCode Copyright String Hash Table Two Pointers

Related Problems

Medium Longest Substring Without Repeating Characters

line 17 don't modify hash

line 34 don't use hash[c]

>

0 to check, it will modify hash size

class Solution {

public:

/\*\*

 \* @param s : A string

 \* @return : The length of the longest substring 

 \*           that contains at most k distinct characters.

 \*/

int lengthOfLongestSubstringKDistinct\(string s, int k\) {

    // write your code here

    if \(s.length\(\) <= k\) {

        return s.length\(\);

    }

    int len = 0;

    int i = 0, j = 0;

    unordered\_map<char, int> hash;

    for \(; i < s.length\(\); ++i\) {

        while \(j < s.length\(\) && CheckValid\(hash, s\[j\], k\)\) {

            ++hash\[s\[j\]\];

            ++j;



            if \(j - i > len\) {

                len = j - i;

            }

        }

        --hash\[s\[i\]\];

        if \(hash\[s\[i\]\] == 0\) {

            hash.erase\(s\[i\]\);

        }

    }

    return len;

}



bool CheckValid\(unordered\_map<char, int> &hash, char c, int k\) {

    if \(hash.size\(\) < k \|\| \(hash.size\(\) == k && hash.find\(c\) != hash.end\(\)\)\) {

        return true;

    } else {

        return false;

    }

}

};