[LeetCode] Unique Length-3 Palindromic Subsequences 자바

문제

 

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/?envType=daily-question&envId=2025-01-04

 

▫️  s 문자열이 주어질 때 3글자의 Palindrome을 만족하는 개수 리턴

▫️ 단, 글자 순서 변경 X, 중복 X

 

 

문제 풀이

 

팰린드롬 문자의 개수가 '3개'로 정해져 있기 때문에 쉽게 구현이 가능하다.

양끝쪽 글자에 대해서 가운데 오는 숫자만 중복없이 구하면 된다.

 

✅ 알고리즘

1. 처음 인덱스와 끝 인덱스를 가르키는 start, end 변수를 선언하여 양끝쪽 문자가 같을 때까지 end-- 하며 반복문을 실행한다.

2. start, end가 가리키는 문자가 동일한 경우 그 사이의 문자들을 돌면서 Set에 중복없이 잡는다.

3. Set에 들어간 개수를 Map객체에 담아둔다.

     → HashMap(양끝쪽문자, 가운데에 들어갈 수 있는 문자 카운트)

4. start++ 하며 Map에 아직 담기지 못한 문자가 있는 경우 계속 반복하여 Map에 담는다.

 

 

소스 코드

 

public static int countPalindromicSubsequence(String s) {
	HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = s.length() - 1;
        
        while(end- start > 1) {
        	char cur = s.charAt(start);
        	
        	//key값 없는 경우
        	if(map.putIfAbsent(cur, 0) == null) {
        		Set<Character> set = new HashSet<>();
        		
        		//end를 줄여가며 start와 같은 글자를 찾음
        		while(start < end) {
        			if(cur == s.charAt(end)){
        				for(int i = start + 1; i < end; i++) 
        					set.add(s.charAt(i));
        				break;
        			}
        			end--;
        		}
        		map.put(cur, set.size());
        	}
        	
        	//key값 만들면 start 전진
        	start++;
        	end = s.length() - 1;
        }
        
        int answer = 0;
        for(int key : map.values())
        	answer += key;
        
        return answer;
    }