하위 문자열을 제거한 후의 최소 문자열 길이

2696. 하위 문자열 제거 후 최소 문자열 길이

난이도: 쉬움

주제: 문자열, 스택, 시뮬레이션

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

이 문자열에 몇 가지 작업을 적용하면 한 번의 작업으로 s에서 하위 문자열 "AB" 또는 "CD" 중 하나를 제거할 수 있습니다.

얻을 수 있는 결과 문자열의 최소가능한 길이를 반환합니다

.

참고

하위 문자열을 제거한 후 문자열이 연결되어 새로운 "AB" 또는 "CD" 하위 문자열이 생성될 수 있습니다.

예 1:

• 입력:
s = "ABFCACDB"
• 출력:
2
• 설명:
  다음 작업을 수행할 수 있습니다.
  하위 문자열 "ABFCACDB"를 제거하여 s = "FCACDB"가 되도록 합니다.
  하위 문자열 "FCACDB"를 제거하여 s = "FCAB"가 되도록 합니다.
  하위 문자열 "FCAB"를 제거하여 s = "FC"가 됩니다.
  따라서 문자열의 결과 길이는 2입니다.
  우리가 얻을 수 있는 최소 길이임을 알 수 있습니다.

예 2:

• 입력:
s = "ACBBD"
• 출력:
5
• 설명:
문자열에 대해 어떤 작업도 수행할 수 없으므로 길이가 동일하게 유지됩니다.

제약조건:

1 s는 영문 대문자로만 구성됩니다.

힌트:

무차별 대입으로 문제를 해결할 수 있나요?
더 이상 항목이 없을 때까지 문자열을 반복적으로 탐색하여 하위 문자열 "AB" 및 "CD"를 찾아서 제거합니다.

해결책:

스택

을 사용하여 하위 문자열 "AB" 및 "CD" 제거를 처리합니다. 스택 접근 방식을 사용하면 문자열을 순회하는 동안 발생하는 이러한 하위 문자열을 효율적으로 제거할 수 있습니다.

접근하다:

1. 스택 사용
   :
   문자열을 문자별로 탐색합니다.
   각 문자를 스택에 넣습니다.
   스택의 상위 두 문자가 하위 문자열 "AB" 또는 "CD"를 형성하는 경우 스택에서 이 두 문자를 팝합니다(제거).
   입력 문자열의 모든 문자에 대해 이 과정을 계속합니다.
2. 최종 문자열
   :
   순회가 끝나면 스택에는 축소된 문자열이 포함됩니다.
   가능한 최소 길이는 스택 크기입니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2696. 하위 문자열 제거 후 최소 문자열 길이

<?php <br>
/**

• @param String $s
• @return Integer /

function minLengthAfterRemovals($s) { ... ... ... /*

• go to ./solution.php */

}

// Example usage:
echo minLengthAfterRemovals("ABFCACDB"); // Output: 2
echo "\n";
echo minLengthAfterRemovals("ACBBD"); // Output: 5
?>

설명:

빈 스택($stack)을 초기화합니다.
문자열 s의 각 문자를 반복합니다.
• 스택의 최상위 문자를 확인하세요.
  맨 위 문자와 현재 문자가 하위 문자열 "AB" 또는 "CD"를 형성하는 경우 array_pop을 사용하여 맨 위 문자를 제거합니다.
  그렇지 않으면 현재 문자를 스택에 푸시합니다.
스택은 가능한 모든 제거 후에도 남아 있는 문자를 보유합니다.
마지막으로 count($stack)는 결과 문자열의 길이를 제공합니다.

복잡성:

• 시간 복잡도
: O(n), 여기서 n은 문자열의 길이입니다. 각 문자는 최대 두 번(푸시 한 번, 팝 한 번) 처리됩니다.
• 공간 복잡도
: 스택의 경우 O(n), 제거가 불가능한 최악의 경우.

이 솔루션은 더 이상 찾을 수 없을 때까지 "AB" 및 "CD"의 가능한 모든 항목을 제거하여 문자열을 효과적으로 최소화합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소

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

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

• 링크드인
• 깃허브

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