<Medium> Longest Substring Without Repeating Characters (LeetCode : C#)

https://leetcode.com/problems/longest-substring-without-repeating-characters/

📕 문제 설명

문자열이 주어졌을 때 같은 문자가 없는 가장 긴 부분 문자열 반환

• Input
  string
• Output
  같은 문자가 없는 가장 긴 부분문자열

예제

풀이

한 문자씩 차례로 보다가 동일한 문자를 만나게 된다. 이전에 나왔던 동일한 문자의 index 다음 문자부터 현재 문자까지를 두고 다시 뒷 문자를 확인하는 방식으로 최대 길이를 계산해나간다.

예를 들면 다음의 문자열이 주어졌을때 "abcadca" 두번째 a를 만나면 bca(index 1~3)를 기준으로 다시 뒷문자 확인하고, 현재 abc에 대한 길이를 answer로 둔다. bcad -> bcadc가 되면 이전 c기준으로 다시 자른다. adc에서 다시 뒷문자를 확인한다. 그리고 길이를 4로 update .. 이런 방식으로 진행되는 코드이다.

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if (s.Length == 0) return 0;
        if (s.Length == 1) return 1;

        Dictionary<char, int> checkDict = new Dictionary<char, int>();
        int answer = 0;

        for (int i = 0; i < s.Length; i++)
        {
            if (checkDict.TryGetValue(s[i], out int val))
            {
                answer = answer > checkDict.Count ? answer : checkDict.Count;
                string currentSub = s.Substring(val + 1, i - val);
                checkDict.Clear();
                for (int j = 0; j < currentSub.Length; j++)
                {
                    checkDict.Add(currentSub[j], j + (val + 1));
                }
                
            }
            else
            {
                checkDict.Add(s[i], i);
            } 
        }

        answer = answer > checkDict.Count ? answer : checkDict.Count;

        return answer;
        
    }
}

결과