[백준] 20437 - 문자열 게임 2

https://www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

문자열이 주어지고, 주어진 조건 2개에 맞는 sub string을 구하는 문제이다.

언뜻 보면 굉장히 다른 두 개의 조건 같지만, 실은 같은 구조의 조건이다.

바로 첫 번째, 마지막 글자가 같고 어떤 문자를 정확히 k개 포함하는 문자열이라는 것이다.

 

첫 번째 조건의 문자열도 위 문장을 적용시킬 수 있다.

 

그렇다면 조건에 맞는 문자열을 구하는 과정을 보자.

먼저 주어지는 문자열을 이용해서 각 알파벳이 어디에 위치하는지를 나타내는 배열을 하나 만들고 다음과 같이 저장하였다.

 

for (int i = 0; i < s.length(); i++) {
	v[s[i] - 'a'].push_back(i);
}

 

문자열에 나올 수 있는 알파벳의 개수는 26개이므로, 모든 알파벳의 위치들을 탐색해 슬라이딩 윈도우 기법으로 최대, 최소 길이를 구해주면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v(26);

int main() {
	int t; cin >> t;
	while (t--) {
		v.clear();
		v.resize(26);
		string s; cin >> s;
		int n; cin >> n;

		for (int i = 0; i < s.length(); i++) {
			v[s[i] - 'a'].push_back(i);
		}

		int ans1 = -1, ans2 = -1;

		for (int i = 0; i < 26; i++) {
			if (v[i].size() < n) continue;
			int k = 0;

			while (k + n - 1 < v[i].size()) {
				if (ans1 == -1 || ans1 > v[i][k + n - 1] - v[i][k] + 1) {
					ans1 = v[i][k + n - 1] - v[i][k] + 1;
				}

				if (ans2 == -1 || ans2 < v[i][k + n - 1] - v[i][k] + 1) {
					ans2 = v[i][k + n - 1] - v[i][k] + 1;
				}

				k++;
			}
		}

		if (ans1 == -1 || ans2 == -1) {
			cout << -1 << '\n';
		}
		else cout << ans1 << ' ' << ans2 << '\n';
	}
}