[2024] day 156. leetcode 2486. Append Characters to String to Make Subsequence

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 3일 (월)
Leetcode daily problem

2486. Append Characters to String to Make Subsequence

https://leetcode.com/problems/append-characters-to-string-to-make-subsequence/?envType=daily-question&envId=2024-06-03

Problem

소문자로만 구성된 두 개의 문자열 s, t 가 주어질 때,
문자열 t가 s의 하위 시퀀스가 되도록 s의 끝에 추가해야 하는 최소 문사수를 반환한다.

하위 시퀀스는 나머지 문자의 순서를 변경하지 않고 일부 문자를 삭제하지 않고 다른 문자열에서 파생될 수 있어야 한다.

Solution

greedy (Two pointers)

해당 문제의 접근방식은 s에 최소한의 문자를 추가해 t를 s의 하위 문자열로 만드는 것이다. 여기서 두 개의 포인터를 사용해서 해결하는데 문자열 s를 순회하는 포인터(i) 와 문자열 t를 순회하는 포인터(j)를 사용한다.

문자열을 탐색하면서 s[i]와 t[j]를 비교하는데, s[i], t[j]가 같다면 두 포인터를 둘 다 증가시키고 s[i]가 t[j]와 다르다면 포인터 i만 증가시킨다. 이 과정을 s나 t의 끝에 도달할 때 까지 반복한다.

루프가 종료된 후에 j는 t의 어느 위치에 매칭되어 있는지 나타내고, t의 남은 문자열 len(t)-j은 s에 추가해야할 문자 수가 된다.

Code

class Solution:
    def appendCharacters(self, s: str, t: str) -> int:
        i, j = 0, 0
        
        while i < len(s) and j < len(t):
            if s[i] == t[j] :
                j +=1
        
            i +=1
        
        
        return len(t) - j

Complexicity

시간 복잡도

s와 t를 한번씩 순회하므로 시간복잡도는 O(n+m) 이다.
여기서 n은 s의 길이, m은 t의 길이이다.

공간 복잡도

추가적인 데이터 구조를 사용하지 않고 단지 두 개의 포인터만 사용했고, 문자열 길이와 무관하게 항상 고정된 개수의 변수만 사용하고 있다. 공간 복잡도는 O(1) 이다.