세 번 발생하는 가장 긴 특수 부분 문자열 찾기 I

2981. 세 번 발생하는 가장 긴 특수 하위 문자열 찾기 I

난이도:중

주제: 해시 테이블, 문자열, 이진 검색, 슬라이딩 윈도우, 계산

영문 소문자로 구성된 문자열 s가 주어졌습니다.

단일 문자로만 구성된 문자열을 특수라고 합니다. 예를 들어 문자열 "abc"는 특별하지 않지만 문자열 "ddd", "zz" 및 "f"는 특별합니다.

s에서 최소 세 번 발생하는 가장 긴 특수 하위 문자열의 길이를 반환하거나, 특수 하위 문자열이 최소한 세 번 발생하지 않으면 -1을 반환합니다.

하위 문자열은 문자열 내의 연속된 비어 있지 않은 문자 시퀀스입니다.

예 1:

• 입력: s = "aaaa"
• 출력: 2
• 설명: 세 번 나타나는 가장 긴 특수 하위 문자열은 "aa"입니다. 하위 문자열은 "aaaa", "aaaa" 및 "aaaa"입니다.
  • 달성 가능한 최대 길이는 2임을 알 수 있습니다.

예 2:

• 입력: s = "abcdef"
• 출력: -1
• 설명: 적어도 세 번 나타나는 특별한 하위 문자열은 없습니다. 따라서 -1을 반환합니다.

예 3:

• 입력: s = "abcdef"
• 출력: 1
• 설명: 세 번 나타나는 가장 긴 특수 하위 문자열은 "a"입니다. 하위 문자열은 "abcaba", "abcaba" 및 "abcaba"입니다.
  • 달성 가능한 최대 길이는 1임을 알 수 있습니다.

제약조건:

• 3
• s는 영문 소문자로만 구성됩니다.

힌트:

1. 제약이 적습니다.
2. 모든 하위 문자열을 무차별 대입 검사합니다.

해결책:

s의 작은 제약(길이 최대 50)으로 인해 무차별 접근 방식을 사용할 수 있습니다. 우리는:

1. 가능한 하위 문자열 길이를 반복합니다(가장 긴 것부터 가장 짧은 것까지).
2. 주어진 길이의 모든 하위 문자열을 확인하고 발생 횟수를 계산하세요.
3. 하위 문자열이 3번 이상 나타나면 특수한 문자열인지(1개의 반복 문자로 구성) 확인하세요.
4. 가장 긴 부분 문자열의 길이를 반환합니다. 조건을 충족하는 하위 문자열이 없으면 -1을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2981. 세 번 발생하는 가장 긴 특수 하위 문자열 찾기 I

<?php
/**
 * @param String $s
 * @return Integer
 */
function maximumLength($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a substring is special
 *
 * @param $substring
 * @return bool
 */
function isSpecial($substring) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo maximumLength("aaaa") . "\n"; // Output: 2
echo maximumLength("abcdef") . "\n"; // Output: -1
echo maximumLength("abcabcabc") . "\n"; // Output: 1
?>

설명:

1. 외부 루프: 가장 긴 것부터 시작하여 가능한 하위 문자열 길이를 반복합니다. 이렇게 하면 가장 긴 특수 하위 문자열을 찾자마자 반환할 수 있습니다.
2. 슬라이딩 윈도우: 각 하위 문자열 길이에 대해 슬라이딩 윈도우 접근 방식을 사용하여 해당 길이의 모든 하위 문자열을 추출합니다.
3. 하위 문자열 계산: 연관 배열($countMap)을 사용하여 각 하위 문자열의 발생 횟수를 저장하고 계산합니다.
4. Special 확인: 도우미 함수 isSpecial은 하위 문자열이 단 하나의 반복 문자로 구성되어 있는지 확인합니다.
5. 결과 반환: 유효한 하위 문자열이 발견되면 해당 길이를 반환합니다. 그렇지 않으면 -1을 반환합니다.

복잡성

• 시간 복잡도: O(n³) 최악의 경우:
  1. n개의 하위 문자열 길이를 반복합니다.
  2. 각 길이에 대해 O(n) 하위 문자열을 추출합니다.
  3. 각 하위 문자열이 특별한지 확인하세요. O(n)시간
  이 걸립니다.
• 공간 복잡도: O(n²) 부분 문자열 계산 맵으로 인해 발생합니다.

이러한 무차별 접근 방식은 제약 조건(n )을 고려할 때 가능합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 세 번 발생하는 가장 긴 특수 부분 문자열 찾기 I의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!