使用散列 C++ 查找具有 k different/unique 个字符的最长子字符串

Question

我遇到了寻找具有 k 个唯一字符的最长子串的问题。例如，给定以下 str=abcbbbddcc，结果应为：

k=2 => bcbbb
k=3 => bcbbbddcc

我为此使用哈希创建了一个函数 table。散列-table 将充当搜索-window。每当当前 window 中的唯一字符超过 k 时，我通过将 windows 的当前 "start" 向右移动来缩小它。否则，我只是扩大 window 的大小。不幸的是，这似乎是我代码中的一个错误，但我仍然找不到它。谁能帮我找到问题所在？我的函数的输出是子字符串的起始索引及其长度，即 substring(start, start+maxSize);。我找到了一些相关的帖子 and python-sol，但仍然没有使用散列的基于 C++ 的解决方案-table。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

typedef std::vector<int> vector;
typedef std::string string;
typedef std::unordered_map<char, int> unordered_map;
typedef unordered_map::iterator map_iter;

vector longestSubstring(const string & str, int k){

    if(str.length() == 0 || k < 0){
        return {0};
    }

    int size = str.length();
    int start = 0;
    unordered_map map;
    int maxSize = 0;
    int count = 0;
    char c;

    for(int i = 0; i < size; i++){
        c = str[i];

        if(map.find(c)!=map.end()){
            map[c]++;
        }
        else{
            map.insert({c, 1});
        }

        while(map.size()>k){
            c = str[start];
            count = map[c];
            if(count>1){
                map[c]--;
            } 
            else{
                map.erase(c);
            }
            start++;
        }

        maxSize = std::max(maxSize, i-start+1);
    }

    return {start, maxSize};
}

Answer 1

在 maxSize = std::max(maxSize, i-start+1); 之前，您必须确保地图大小恰好是 k - 您永远无法到达 k 但当前代码会立即更新 maxSize 。

还要记住自己 max 代码中的 start 值

    if (map.size() == k) 
        if (i - start + 1 > maxSize) {
            maxSize = i - start + 1;
            astart = start;
        }
...
return {astart, maxSize};

Ideone check

使用散列 C++ 查找具有 k different/unique 个字符的最长子字符串

finding the longest substring with k different/unique characters using hash c++

c++

string

algorithm

hashtable