[LeetCode] 1624. Largest Substring Between Two Equal Characters

https://leetcode.com/problems/largest-substring-between-two-equal-characters/description/

Largest Substring Between Two Equal Characters - LeetCode

leetcode - Largest Substring Between Two Equal Characters

문제 유형 : 문자열 처리, 해싱

문제 난이도 : Easy

 

문제

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

A substring is a contiguous sequence of characters within a string.

 

문자열 s가 주어진다. 두 개의 같은 두 문자 사이의 가장 긴 부분 문자열의 길이를 구하시오. 

두 문자는 세외합니다. 그런 부분 문자열이 없으면, -1을 반환하시오.

부분 문자열은 문자열의 인접한 문자열들이 차례로 있는 것을 말합니다.

 

 

풀이

map에 각 문자들이 처음 나온 인덱스를 저장한다.

보통 map 자료구조의 value 숫자 값의 기본값이 0이므로, 0-indexed에서 1-indexed로 바꿔주기 위해 1을 더한 값을 저장시킨다.

만약 처음 나온 인덱스가 아니라면, 현재 인덱스에서 기존 해시 테이블에 있는 맨 처음 등장한 위치를 뺀 값이 부분 문자열의 길이이다.

따로 변수에 담고, 매번 순회하면서 업데이트하면 된다. 처음에는 -1로 초기화해주면 되겠다.

마지막으로, 최대값을 반환한다.

 

 

코드

C++

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        const int n = s.size();
        unordered_map<char, int> um;
        int maxGap = -1;

        for(int i = 0; i < n; i++) {
            if(um[s[i]]) maxGap = max(maxGap, i - um[s[i]]);
            else um[s[i]] = i+1;
        }

        return maxGap;
    }
};