23114 LeetCode 문제 풀이

1930. Unique Length-3 Palindromic Subsequences

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/?envType=daily-question&envId=2023-11-14

 

1) 문제 설명

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".

Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

 

2) 제한 사항

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

 

3) 도전 과제

X

 

4) 풀이

아래와 같이 접근하였다.

1. 중복되는 알파벳을 찾는다.

2. 중복되는 알파벳의 양 끝 값을 찾는다.

3. 두 값 사이에 있는 중복되지 않는 값들을 결과값에 추가한다.

 

처음에는 3개의 인덱스로 주어진 배열을 3번 순회하여 풀려고 하였다.

그러면 시간 복잡도가 최소 O(n^3) 이라 배열을 덜 순회하는 방법을 택하였다.

 

그런데 결과에서 메모리 사용률이 박살난 걸 보니 그렇게 좋은 접근은 아니었던 것 같다.

 

다른 풀이를 보니 hashMap 대신 배열을 사용할 수 있었을수도..?

 

5) 소스 코드 및 결과

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

class Solution {
    public int countPalindromicSubsequence(String s) {
        char[] charArray = s.toCharArray();
        HashMap<Character, ArrayList<Integer>> indexMap = new HashMap<>();
        HashMap<Character, Integer> charMap = new HashMap<>();

        int index = 0;
        int result = 0;

        // 첫 순회로 indexMap에 인덱스 기록
        for(char c : charArray){
            if(indexMap.containsKey(c)){
                ArrayList<Integer> valueList = indexMap.get(c);
                valueList.add(index++);
                continue;
            }

            ArrayList<Integer> valueList = new ArrayList<>();
            valueList.add(index++);
            indexMap.put(c, valueList);
        }

        Set<Character> keySet = indexMap.keySet();

        // 같은 값이 2개 이상일 경우, 양 끝 값 사이의 중복되지 않은 갯수를 결과값에 더함.
        for(Character key : keySet){
            ArrayList<Integer> valueList = indexMap.get(key);

            if(valueList == null){
                continue;
            }

            if(valueList.size() > 1){
                int startIndex = valueList.get(0);
                int endIndex = valueList.get(valueList.size()-1);

                for(int i = startIndex+1; i<endIndex; i++){
                    char c = charArray[i];
                    if(charMap.containsKey(c)){
                        continue;
                    }
                    charMap.put(c, 1);
                    result++;
                }

                charMap.clear();
            }
        }

        return result;
    }
}

6) 다른 사람의 풀이

class Solution {
    public int countPalindromicSubsequence(String inputString) {
        // Arrays to store the minimum and maximum occurrences of each character in the input string
        int[] minExist = new int[26];
        int[] maxExist = new int[26];
        for (int i = 0; i < 26; i++) {
            minExist[i] = Integer.MAX_VALUE;
            maxExist[i] = Integer.MIN_VALUE;
        }

        // Populate minExist and maxExist arrays
        for (int i = 0; i < inputString.length(); i++) {
            int charIndex = inputString.charAt(i) - 'a';
            minExist[charIndex] = Math.min(minExist[charIndex], i);
            maxExist[charIndex] = Math.max(maxExist[charIndex], i);
        }

        // Variable to store the final count of unique palindromic subsequences
        int uniqueCount = 0;

        // Iterate over each character in the alphabet
        for (int charIndex = 0; charIndex < 26; charIndex++) {
            // Check if the character has occurred in the input string
            if (minExist[charIndex] == Integer.MAX_VALUE || maxExist[charIndex] == Integer.MIN_VALUE) {
                continue; // No occurrences, move to the next character
            }

            // Set to store unique characters between the minimum and maximum occurrences
            HashSet<Character> uniqueCharsBetween = new HashSet<>();

            // Iterate over the characters between the minimum and maximum occurrences
            for (int j = minExist[charIndex] + 1; j < maxExist[charIndex]; j++) {
                uniqueCharsBetween.add(inputString.charAt(j));
            }

            // Add the count of unique characters between the occurrences to the final count
            uniqueCount += uniqueCharsBetween.size();
        }

        // Return the total count of unique palindromic subsequences
        return uniqueCount;
    }
}

배열을 이용한 풀이인데, 시간이 약 1.5배 정도 더 걸리는 대신 메모리 사용률이 15% 정도 적다.