1156. Swap For Longest Repeated Character Substring / TypeScript

You are given a string text. You can swap two of the characters in the text.

Return the length of the longest substring with repeated characters.

 

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa" with length 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.

Example 3:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.

 

출처 : https://leetcode.com/problems/swap-for-longest-repeated-character-substring/description/

 

풀이

function maxRepOpt1(text: string): number {
    if (text.length <= 1) return text.length;
    let maxValue = 0;
    let maxReturnValue = 0;
    let startingIndex = 0;
    let subIndex = 0;
    let currentLetter = '&';

    for (let i = 0; i < text.length - 1; i++) {
        if (maxValue === 0) startingIndex = i;
        maxValue++;
        if (text[i] !== text[i + 1]) {
            currentLetter = text[i];
            //end of the chain
            //test if jumping that value can help ?
            subIndex = i + 2;
            if (text[i] === text[subIndex]) {
                maxValue++;
                //it is equal we can continue
                while (subIndex < (text.length - 1) && text[subIndex] === text[subIndex + 1]) {
                    maxValue++;
                    subIndex++;
                }
            }
            // need to check before and after if we have a value we can swap to increase by 1
            const textBefore = text.substring(0, startingIndex - 1);
            const textAfter = text.substring(subIndex + 1, text.length);

            if (textBefore.includes(currentLetter) || textAfter.includes(currentLetter)) maxValue++;
            maxReturnValue = Math.max(maxValue, maxReturnValue);
            maxValue = 0;
        }
    }

    if (text[text.length - 2] === text[text.length - 1]) {
        if (startingIndex > 0) {
            const textBefore = text.substring(0, startingIndex - 1);
            if (textBefore.includes(text[text.length - 1])) maxValue++;
        }
        maxValue++;
    };

    return Math.max(maxValue, maxReturnValue);

};

 

문자열 text가 "ababa"인 경우

1. 초기 상태:
   • maxValue = 0
   • maxReturnValue = 0
   • startingIndex = 0
   • subIndex = 0
   • currentLetter = '&'
2. 첫 번째 반복 (i = 0):
   • maxValue가 0이므로 startingIndex = 0
   • maxValue++ => maxValue = 1
   • text[0] ('a')와 text[1] ('b')가 다르므로:
     • currentLetter = 'a'
     • subIndex = 2 (i + 2)
     • text[0] ('a')와 text[2] ('a')가 같으므로:
       • maxValue++ => maxValue = 2
       • subIndex = 2
       • text[2] ('a')와 text[3] ('b')가 다르므로 내부 while 루프는 종료.
     • textBefore = "" (시작 인덱스 이전의 문자열)
     • textAfter = "ba" (subIndex 이후의 문자열)
     • textBefore나 textAfter에 currentLetter ('a')가 포함되어 있으므로 maxValue++ => maxValue = 3
     • maxReturnValue = Math.max(3, 0) => maxReturnValue = 3
     • maxValue = 0
3. 두 번째 반복 (i = 1):
   • maxValue가 0이므로 startingIndex = 1
   • maxValue++ => maxValue = 1
   • text[1] ('b')와 text[2] ('a')가 다르므로:
     • currentLetter = 'b'
     • subIndex = 3 (i + 2)
     • text[1] ('b')와 text[3] ('b')가 같으므로:
       • maxValue++ => maxValue = 2
       • subIndex = 3
       • text[3] ('b')와 text[4] ('a')가 다르므로 내부 while 루프는 종료.
     • textBefore = "a" (시작 인덱스 이전의 문자열)
     • textAfter = "a" (subIndex 이후의 문자열)
     • textBefore나 textAfter에 currentLetter ('b')가 포함되어 있으므로 maxValue++ => maxValue = 3
     • maxReturnValue = Math.max(3, 3) => maxReturnValue = 3
     • maxValue = 0
4. 세 번째 반복 (i = 2):
   • maxValue가 0이므로 startingIndex = 2
   • maxValue++ => maxValue = 1
   • text[2] ('a')와 text[3] ('b')가 다르므로:
     • currentLetter = 'a'
     • subIndex = 4 (i + 2)
     • text[2] ('a')와 text[4] ('a')가 같으므로:
       • maxValue++ => maxValue = 2
       • subIndex = 4
     • textBefore = "ab" (시작 인덱스 이전의 문자열)
     • textAfter = "" (subIndex 이후의 문자열)
     • textBefore에 currentLetter ('a')가 포함되어 있으므로 maxValue++ => maxValue = 3
     • maxReturnValue = Math.max(3, 3) => maxReturnValue = 3
     • maxValue = 0
5. 네 번째 반복 (i = 3):
   • maxValue가 0이므로 startingIndex = 3
   • maxValue++ => maxValue = 1
   • text[3] ('b')와 text[4] ('a')가 다르므로:
     • currentLetter = 'b'
     • subIndex = 5 (i + 2)
     • subIndex가 문자열 길이를 초과하므로 내부 조건문 종료.
     • textBefore = "aba" (시작 인덱스 이전의 문자열)
     • textAfter = "" (subIndex 이후의 문자열)
     • textBefore에 currentLetter ('b')가 포함되어 있으므로 maxValue++ => maxValue = 2
     • maxReturnValue = Math.max(3, 2) => maxReturnValue = 3
     • maxValue = 0
6. 마지막 문자 검사:
   • text[3] ('b')와 text[4] ('a')가 다르므로 별도의 처리 없이 종료.

최종적으로 maxReturnValue는 3이므로, 함수는 3을 반환.

따라서, "ababa" 문자열에서 한 번의 교환으로 최대 연속 문자 길이는 3