1750_java.md

1750. Minimum Length of String After Deleting Similar Ends

Summary

🙇‍♂️ URL : https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/
🤷‍♂️ Difficulty: Medium
💆‍♂️ Submissions

• RunTime: 1178 ms, faster than 5.23% of Java online submissions
• Memory Usage: 39.2 MB, less than 88.37% of Java online submissions

Source code

class Solution {
    public int minimumLength(String s) {
        ArrayList<Character> str = new ArrayList<>();
        for(int i=0; i<s.length(); i++) {
            str.add(s.charAt(i));
        }
        while(str.size() > 0) {
            if((str.size() == 1) || (str.get(0) != str.get(str.size()-1))) {
                break;
            }

            char fval = str.get(0);
            char eval = str.get(str.size()-1);

            while(str.size() > 0 && fval == str.get(0)) {
                str.remove(0);
            }

            while(str.size() > 0 && eval == str.get(str.size()-1)) {
                str.remove(str.size()-1);
            }
        }
        return str.size();
    }
}

How to Approach

문자열의 양 끝(처음과 마지막)이 동일할 때, 해당 문자를 삭제해서 최종적으로 남는 문자열의 길이를 측정하는 문제다.

테스트케이스 3번과 같이 "aabccabba" 문자열이 주어지면, 다음의 순서로 값이 만들어진다.

An optimal sequence of operations is:

• Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
• Take prefix = "b" and suffix = "bb" and remove them, s = "cca".

그래서 맨 앞과 맨 뒷 글자가 동일할 경우, 각 지점(처음과 끝)에서 각각 동일하지 않은 문자가 나올때까지 계속 삭제해서 맨앞과 맨뒤가 동일하지 않은 문자가 나올 때까지 이를 반복해주는 코드를 작성했다. 문자열에서 바로 하는것이 쉽지 않을 것 같아 ArrayList를 별도로 만들어서 구현하였다.

먼저 앞을 다 확인하고 그 다음 뒤를 확인하는 코드를 작성하였는데, 만약 baaaaaaaab인 경우 a일때 이미 모든 문자를 다 지워버리므로 각 경우마다 문자열 사이즈가 0보다 큰지 먼저 확인하고 같은 문자를 순차적으로 삭제하도록 하였다. 해당 조건을 입력하지 않았을 때에는 계속 NullpointException 오류가 나왔다.

좀 더 빠르게 풀 수 있을 것 같은데, 더 좋은 방법을 찾기 위해 꾸준히 공부해야할 것 같다.