11/14 (화) 대소문자를 모두 가지는 최장 부분 문자열 구하기 TIL

공부한 것

• LeetCode #1763. Longest Nice Substring

  Longest Nice Substring - LeetCode

  Can you solve this real interview question? Longest Nice Substring - A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear. However, "abA" is not because 'b' appears, but 'B' does not. Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.   Example 1: Input: s = "YazaAay" Output: "aAa" Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear. "aAa" is the longest nice substring. Example 2: Input: s = "Bb" Output: "Bb" Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring. Example 3: Input: s = "c" Output: "" Explanation: There are no nice substrings.   Constraints: * 1 <= s.length <= 100 * s consists of uppercase and lowercase English letters.

  https://leetcode.com/problems/longest-nice-substring/description/

  

  • Divide and Conquer(분할 정복법)를 이해하기에 아주 좋은 다이어그램이 있어 가져와보았다:

    

    출처: https://leetcode.com/problems/longest-nice-substring/solutions/2237699/javascript-brute-force-and-divide-and-conquer-with-illustrations/

  • 해답 코드:

    // Divide and Conquer 풀이: 
    function longestNiceSubstring2(s: string): string {
    	// 탈출 조건: s의 길이가 0 혹은 1인 경우, 대-소문자 짝이 있을 수 없으므로 (최장 부분 문자열은)빈 문자열 반환.
    	if (s.length < 2)
    		return '';
    
    	let arr = [...s];
    	let set = new Set(arr);
    
    	for (let i = 0; i < arr.length; i++) {
    		const c = arr[i];
    		// 현재 문자 c의 대소문자 버전이 모두 현재 부분 문자열 s에 존재하면: 현재 부분 문자열 s의 다음 문자 검사를 계속한다(=s를 둘로 쪼개지 않는다).  
    		if (set.has(c.toUpperCase()) && set.has(c.toLowerCase()))
    			continue;
    
    		// 현재 문자 c의 대소문자가 현재 부분 문자열 s에 들어있지 않으면: 현재 문자 c를 기준으로 반절을 가른 부분 문자열 각각에서 최장 부분 문자열을 추출한다. s의 길이가 < 2에 도달할 때까지 반복하게 됨.
    		const sub1: string = longestNiceSubstring2(s.substring(0, i));
    		const sub2: string = longestNiceSubstring2(s.substring(i + 1));
    
    		// 두 (최장)부분 문자열 중 길이가 더 긴 쪽을 반환한다.
    		return sub1.length >= sub2.length ? sub1 : sub2;
    	}
    
    	return s;
    }

Uploaded by N2T