題目

對(duì)于一個(gè)字符串,請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法，找到字符串的最長(zhǎng)無重復(fù)字符的子串長(zhǎng)度。

給定一個(gè)字符串A及它的長(zhǎng)度n，請(qǐng)返回它的最長(zhǎng)無重復(fù)字符子串長(zhǎng)度。保證A中字符全部為小寫英文字符，且長(zhǎng)度小于等于500。

思路

• DP思想：最優(yōu)子結(jié)構(gòu)、重復(fù)子問題
• Hash：存儲(chǔ)上一個(gè)位置，輔助DP進(jìn)行

答案

    int longestSubstring(string A, int n) {
        // 存儲(chǔ)上一個(gè)重復(fù)字符的位置
        int *lastPosition = new int[256];
        for (int i = 0; i < 256; i++) {
            lastPosition[i] = -1;
        }

        // 動(dòng)態(tài)規(guī)劃過程
        int previous = -1;// 前一個(gè)的最長(zhǎng)子串左節(jié)點(diǎn)位置
        int current = 0;
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            previous = max(previous, lastPosition[A[i]]);
            current = i - previous;
            maxLength = max(current, maxLength);
            lastPosition[A[i]] = i;
        }
        return maxLength;
    }