작업 후 문자열의 최소 길이

3223. 연산 후 문자열의 최소 길이

난이도:중

주제: 해시 테이블, 문자열, 계산

문자열 s가 주어졌습니다.

다음 프로세스는 무엇이든 횟수에 관계없이 수행할 수 있습니다.

• 인덱스 i 왼쪽에 s[i]와 동일한 문자가 최소 한 문자 있고 최소 한 문자가 있도록 문자열에서 인덱스 i를 선택합니다. 오른쪽에는 s[i]와도 같습니다.
• s[i]와 동일한 인덱스 i의 왼쪽에 있는 가장 가까운 문자를 삭제합니다.
• s[i]와 동일한 인덱스 i의 오른쪽에 있는 가장 가까운 문자를 삭제합니다.

달성할 수 있는 최종 문자열 s의 최소 길이를 반환합니다

.

예 1:

• 입력:
s = "abaacbcbb"
• 출력:
5
• 설명:
  우리는 다음 작업을 수행합니다.
  인덱스 2를 선택한 다음 인덱스 0과 3의 문자를 제거합니다. 결과 문자열은 s = "bacbcbb"입니다.
  인덱스 3을 선택한 다음 인덱스 0과 5의 문자를 제거합니다. 결과 문자열은 s = "acbcb"입니다.

예 2:

• 입력:
s = "aa"
• 출력:
2
• 설명:
어떠한 연산도 수행할 수 없으므로 원래 문자열의 길이를 반환합니다.

제약조건:

• ^{1 5}
s는 영문 소문자로만 구성됩니다.

힌트:

최종 답을 찾는 데에는 각 문자의 빈도만이 중요합니다.
캐릭터가 3회 미만 등장할 경우 해당 캐릭터에 대한 처리가 불가능합니다.
문자열에 3번 이상 나타나는 문자가 있다고 가정하면 해당 문자가 최대 2번 남을 때까지 이 문자 중 2개를 반복적으로 삭제할 수 있습니다.

해결책:

문자열에서 각 문자의 빈도에 초점을 맞춰야 합니다. 이를 해결하는 방법은 다음과 같습니다.

접근하다:

1. 문자 빈도 계산

   :
   빈도표를 사용하여 문자열에 각 문자가 나타나는 횟수를 계산합니다.

2. 빈도 >= 3으로 문자 줄이기

   :
   한 문자가 3번 이상 나타나면 2번만 남을 때까지 두 번 반복해서 삭제할 수 있습니다.

3. 최소 길이 계산

   :
   • 빈도를 줄인 후 모든 캐릭터의 남은 수를 합산해 보세요.

이 솔루션을 PHP로 구현해 보겠습니다: 3223. 연산 후 문자열의 최소 길이

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

// Example 1
$s1 = "abaacbcbb";
echo "Input: $s1\n";
echo "Output: " . minimumLength($s1) . "\n";

// Example 2
$s2 = "aa";
echo "Input: $s2\n";
echo "Output: " . minimumLength($s2) . "\n";
?>

설명:

1. 빈도수:

   • 문자열을 반복하고 각 문자에 대해 $주파수 배열의 개수를 늘립니다.

2. 문자수 감소:

   • $주파수 배열의 각 문자에 대해 개수가 3 이상인지 확인하세요. 그렇다면 최대 2개로 줄이세요.

3. 결과 계산:

   • $주파수 배열의 값을 합하여 가능한 최소 문자열 길이를 구합니다.

예제 연습:

예시 1:

• 입력: s = "abaacbcbb"
• 빈도: ['a' => 3, 'b' => 4, 'c' => 2]
• 감소 후:
  • 'a' => 2(3에서 감소),
  • 'b' => 2(4에서 감소),
  • 'ㄷ' => 2(감소 필요 없음).
• 최소 길이: 2 2 2 = 6.

예 2:

• 입력: s = "aa"
• 빈도: ['a' => 2]
• 3개 이상의 빈도를 갖는 캐릭터가 없으므로 감소가 필요하지 않습니다.
• 최소 길이: 2.

복잡성:

1. 시간 복잡성:

   • 빈도 계산: O(n), 여기서 n은 문자열의 길이입니다.
   • 축소: O(1) (소문자는 26개뿐이므로 상수 시간).
   • 합산 주파수: O(1).
   • 전체: O(n).

2. 공간 복잡성:

   • O(1), 주파수 배열에 최대 26개의 항목이 있기 때문입니다.

이 솔루션은 효율적이며 문제의 제약 내에서 잘 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 작업 후 문자열의 최소 길이의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!