K개의 서로 다른 모음을 가진 가장 긴 부분 문자열

이 기사에서는 주어진 문자열에서 K개의 서로 다른 모음을 포함하는 가장 긴 부분 문자열을 찾는 문제를 탐구합니다. 이 문제는 C++에서 다른 알고리즘을 사용하여 해결될 수 있습니다. 이 문제는 컴퓨터 과학 분야, 특히 텍스트 처리 및 자연어 처리 작업에서 자주 발생합니다. 문자열을 조작하고 극단적인 경우를 처리하는 사람의 능력을 검사합니다.

문법

C++ 필드에서 std::string 클래스는 문자열 데이터 유형을 나타냅니다. 이 다목적 엔터티는 문자 시퀀스를 저장하고 조작하는 데 사용할 수 있습니다.

템플릿 클래스 std::벡터는 동적 배열의 특성을 구현하므로 배열 크기를 조정하고 캡슐화된 요소에 대해 일련의 작업을 수행할 수 있습니다.

클래스 템플릿인 std::unordered_map은 순서가 지정되지 않은 매핑 구조를 캡슐화합니다. 키가 일치하지 않는 단일 키-값 쌍을 저장할 수 있으며 이러한 다른 키를 사용하여 값을 검색할 수 있습니다.

함수 템플릿 std::max는 최대 두 값을 반환합니다. 이 다목적 메커니즘을 사용하면 > 연산자가 올바르게 정의된 한 모든 데이터 유형을 쉽게 비교할 수 있습니다.

알고리즘

• 시작

• 가장 긴 부분 문자열과 그 길이를 저장하려면 변수를 초기화하세요.

• 문자열을 반복하여 K개의 서로 다른 모음이 포함된 하위 문자열을 찾습니다.

• 부분 문자열의 길이를 비교하고 그에 따라 가장 긴 부분 문자열과 그 길이를 업데이트하세요.

• 모든 하위 문자열이 평가될 때까지 2단계와 3단계를 반복합니다.

• 가장 긴 부분 문자열을 반환합니다.

• 끝

방법

• 방법 1 - 무차별 대입

• 방법 2 − 슬라이딩 창

방법 1: 무차별 크래킹

이 구현은 정확히 k개의 고유 모음이 있는 문자열의 가장 긴 부분 문자열을 찾기 위한 무차별 대입 방법을 구현합니다. 코드는 is_vowel 및 has_k_distinct_vowels라는 두 가지 도우미 함수를 정의하는 것으로 시작됩니다.

Example

Example

is_vowel 함수는 단일 문자를 입력으로 받고 해당 문자가 모음(예: 'a', 'e', ​​​​'i', 'o' 또는 'u')인 경우 참 값을 반환하고 거짓 값을 반환합니다. 그렇지 않으면. 이 함수는 나중에 문자가 모음인지 여부를 확인하는 데 사용되었습니다.

has_k_distinct_vowels 함수는 문자열과 정수 k를 입력으로 받아들이고 문자열에 정확히 k개의 고유 모음이 포함되어 있으면 참 값을 반환하고, 그렇지 않으면 거짓 값을 반환합니다. 이 함수는 unordered_set을 사용하여 문자열에 모음을 기록하고 문자열에 있는 고유 모음 수를 계산합니다.

메인 함수 maximum_substring_bruteforce는 문자열과 정수 k를 입력으로 받고 정확히 k개의 고유 모음을 포함하는 문자열에서 가장 긴 부분 문자열을 반환합니다.

이는 두 개의 중첩 for 루프를 활용하여 문자열의 가능한 모든 하위 문자열을 반복함으로써 달성됩니다. 각 부분 문자열에 대해 has_k_distinct_vowels 함수를 호출하여 부분 문자열에 정확히 k개의 고유 모음이 있는지 확인합니다.

현재 하위 문자열에 k개의 고유 모음이 있고 현재 가장 긴 하위 문자열보다 넓은 경우 현재 하위 문자열이 새로운 가장 긴 하위 문자열이 됩니다.

마지막으로 코드는 문자열과 정수 k를 입력하고,longest_substring_bruteforce 함수를 호출하여 k개의 고유 모음이 있는 가장 긴 부분 문자열을 찾아 결과를 출력합니다.

출력

방법 2: 슬라이딩 윈도우

슬라이딩 윈도우 방식은 컴퓨터 과학 및 알고리즘 문제를 해결하는 데 사용되는 기술입니다. 주어진 입력에서 특정 기준을 충족하는 하위 문자열 또는 하위 배열과 같은 특정 패턴을 찾는 데 사용됩니다.

이 방법에서는 두 개의 포인터를 사용하여 입력에 따라 슬라이드되는 슬라이딩 창을 만듭니다. 필요한 조건이 충족되도록 창 크기는 필요에 따라 조정됩니다. 알고리즘은 고유 요소 수, 요소 합계 등과 같은 현재 창의 속성을 추적합니다.

Example

Example

is_vowel 함수는 주어진 문자가 모음(예: a, e, i, o 또는 u)인 경우 true를 반환하는 도우미 함수입니다.

메인 함수 maximum_substring_slidingwindow는 문자열 s와 정수 k를 입력으로 받아들입니다. 왼쪽과 오른쪽 두 개의 포인터를 사용하여 슬라이딩 창을 만들고 문자열을 반복합니다.

순서가 지정되지 않은 지도 주파수를 사용하여 현재 창에서 각 모음의 빈도를 추적하세요. 창에 있는 모음의 빈도가 k를 초과하면 모음의 빈도가 다시 k와 같아질 때까지 왼쪽 포인터를 오른쪽으로 이동합니다. 현재 창의 길이는 오른쪽 - 왼쪽 + 1로 계산되며, 지금까지 본 최대 길이보다 큰 경우 시작 인덱스와 길이가 업데이트됩니다.

마지막으로 함수는 String 클래스의 substr 메소드를 사용하여 k개의 서로 다른 모음을 포함하는 가장 긴 하위 문자열을 반환합니다.

#include <iostream>
#include <string>
#include <unordered_map>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

std::string longest_substring_slidingwindow(const std::string &s, int k) {
   int left = 0, right = 0, max_len = 0, start = 0;
   std::unordered_map<char, int> freq;

   while (right < s.size()) {
      char c = s[right];
      if (is_vowel(c)) {
         freq[c]++;
      }

      while (freq.size() > k) {
         char left_char = s[left];
         if (is_vowel(left_char)) {
            freq[left_char]--;
            if (freq[left_char] == 0) {
               freq.erase(left_char);
            }
         }
         left++;
      }

      if (freq.size() == k && (right - left + 1) > max_len) {
         max_len = right - left + 1;
         start = left;
      }

      right++;
   }

   return s.substr(start, max_len);
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_slidingwindow(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

输出

Longest substring with 3 distinct vowels: iaaioooaa

结论

在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。

위 내용은 K개의 서로 다른 모음을 가진 가장 긴 부분 문자열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!