문제 설명
a 및 b 두 개의 문자열이 주어지면 a 및 b 사이의 **가장 길고 흔하지 않은 하위 시퀀스*의 길이를 반환합니다. 가장 긴 흔하지 않은 하위 시퀀스가 ​​존재하지 않으면 -1 를 반환합니다.

두 문자열 사이의 흔하지 않은 하위 시퀀스는 하나의 하위 시퀀스이지만 다른 하나는 아닌 문자열입니다.

문자열 s 의 하위 시퀀스는 s 에서 임의 개수의 문자를 삭제한 후 얻을 수 있는 문자열입니다.

예를 들어, "abc"는 "aebdc"에서 밑줄 친 문자를 삭제하여 "aebdc"를 얻을 수 있기 때문에 "abc"의 하위 시퀀스입니다. "aebdc"의 다른 하위 시퀀스에는 "aebdc" , "aeb" 및 "" (빈 문자열)이 포함됩니다.

예 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

예 2:

Input: a = "aaa", b = "bbb"
Output: 3
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

예 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a.

제약:

1 <= a.length, b.length <= 100

a 및 b는 영문 소문자로 구성됩니다.

아이디어

Brute Force Solution: Generate all the subsequences of both the strings and store the frequency of each subsequence in a hashmap/dictionary. The subsequence whose frequency equal to 1 will be the longest uncommon subsequence. If there is not subsequence with frequency as 1 , then there is no uncommon subsequence for given strings.

Optimized Solution:

1. If both the given strings are equal then there will not be uncommon subsequences for given strings. In this case we can directly return -1
2. If the strings are not equal and length of both the strings are equal , then one string cannot be the subsequence of other string. In this case we can either return length of any one of the strings.
3. If both strings are not equal and length of one string is greater than length of other string, then in this case we can directly return the length of the largest string as the largest string cannot be the subsequence of the smaller string.

코드(파이썬)

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        a_length = len(a)
        b_length = len(b)
        return max(a_length,b_length)

아래 git repo에는 leetcode 및 interviewbit의 몇 가지 중요한 프로그래밍 질문과 솔루션이 포함되어 있습니다.

Dheerajthodupunoori / 문제 해결

문제 해결 질문 및 솔루션.

문제 해결

이 리포지토리에는 제품 기반 회사 인터뷰에 중요한 몇 가지 중요한 데이터 구조 및 알고리즘 질문이 포함되어 있습니다.
현재 이 저장소에는 그래프 데이터 구조 및 연결 목록에 대한 몇 가지 질문이 포함되어 있습니다. 곧 더 추가할 예정입니다.
자유롭게 이 저장소에 기여해 주세요.


View on GitHub