제목 링크

Leetcode

제목 설명

중복된 문자가 없는 하위 문자열의 길이를 구하려면 문자열 (a~z만 포함) 을 입력하십시오.예를 들어 arabcacfr의 경우 가장 긴 중복된 문자가 없는 하위 문자열은 acfr이고 길이는 4이다.

문제풀이의 방향

동적 계획.먼저 dp[i]를 정의하면 i번째 문자로 끝나는 중복된 문자를 포함하지 않는 하위 문자열의 최대 길이를 나타냅니다.만약 i번째 문자가 나타나지 않았다면 dp[i] = dp[i-1] + 1;만약에 i자 이전에 나타났다면 우리는 상황을 나누어 토론해야 한다. 만약에 나타난 위치와 현재 위치의 거리 d<=dp[i-1], 즉 나타난 위치가 i-1의 가장 긴 문자열에 있다면 이때 dp[i]=d;그렇지 않으면 i-1의 가장 긴 문자열을 제외하고 dp[i] = dp[i-1] + 1

class Solution {
    public int lengthOfLongestSubstring(String str) {
        if (str==null || str.length()==0) return 0;
        int n = str.length(), maxLen = 1;
        int[] dp = new int[n], pos = new int[256];
        Arrays.fill(pos, -1);
        dp[0] = 1;
        pos[str.charAt(0)] = 0;
        for (int i=1;i<n;i++) {
            int idx = str.charAt(i);
            int lastPos = pos[idx];
            int distance = lastPos==-1? Integer.MAX_VALUE: i-lastPos;
            if (lastPos==-1 || distance>dp[i-1]) dp[i] = dp[i-1] + 1;
            else dp[i] = distance;
            maxLen = Math.max(maxLen, dp[i]);
            pos[idx] = i;
        }
        return maxLen;
    }
}