[LeetCode] 2486. Append Characters to String to Make Subsequence

https://leetcode.com/problems/append-characters-to-string-to-make-subsequence/description/

leetcode - Append Characters to String to Make Subsequence

문제 유형 : 문자열처리, 그리디

문제 난이도 : Medium

문제 

You are given two strings s and t consisting of only lowercase English letters.

Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

영소문자로 구성된 두 문자열 s와 t가 있다.

t가 s의 subsequence가 되기 위한 추가로 붙여야 하는 최소 글자수를 말하시오.

순서를 변경하지 않고 잘라서 얻을 수 있는 문자열을 말합니다.

 

풀이

순서를 따르기 때문에, s에 기존에 존재하는 최대 t의 prefix길이를 구해야 한다.

 

코드

C++

class Solution {
public:
    int appendCharacters(string s, string t) {
        if(s == t) return 0;
        int n = s.size();
        int m = t.size();
        
        int i = 0, j = 0;
        while(i < n) {
            while(i < n && j < m && s[i] == t[j]) {
                i++;
                j++;
            }
            i++;
        }
        
        return m - j;
    }
};