There is a necklace of n beads strung in a circle.
Each bead has one lowercase English letter on it, and the i-th character of the necklace string S is the i-th bead.
Because the necklace is round, the 1st bead comes again after the n-th bead.
You want to cut out some consecutive beads so that you have every letter of string T, at least as many times as it appears in T.
The beads you cut out start at some bead and continue in the direction of increasing numbers (after the n-th comes the 1st), and the same bead cannot be used twice.
Cut out as few beads as possible.
If there are several ways, choose the one whose starting bead has the smallest number.
Print the number of the starting bead and the number of beads cut out on one line, separated by a space.
If no cut works, print -1.
Input
The first line has S and the second line has T. Both consist of lowercase English letters only. 1 ≤ length n of S ≤ 100,000, 1 ≤ length of T ≤ 100,000
Output
The number of the starting bead and the number of beads on one line, separated by a space, or -1
Example 1 · stdin
cabbad
dc
stdout
6 2
Example 2 · stdin
ab
aa
stdout
-1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Solve it with two pointers (a sliding window): extend the right end one by one, decreasing 'how many more are needed' (need) for each letter, and once nothing is missing (missing == 0) pull the left end in while its bead is extra. Both ends only move forward, so it is O(n). Treat the round necklace as two laps joined into one line — the bead at position i is S[i % n], so the string does not have to be joined for real. Trap one: on two laps, not capping the window at n beads counts the same bead twice — in the second example "ab", "aba" seems to have two a's, but there is only one a bead, so the answer is -1. Trap two: looking at a single line misses windows that join the last bead (d) and the first bead (c), as in the first example (start at 6, 2 beads). Trap three: switching to <= on equal lengths leaves the last window found — windows come out in order of their start, so replace only on < (windows starting at n or later repeat a window from the first lap, so leave them out). Trap four: looking only at which letters T has is wrong — "aab" needs two a's. Turning a letter into 0–25 differs by language: Python ord(ch) - 97, JavaScript and TypeScript s.charCodeAt(i) - 97, Java, C#, C and C++ compute with characters as integers, so ch - 'a', and in Craykon s[i] is a one-character string, so Str.Code(s[i]) - 97. C reads with a width as in scanf("%100001s", s), and Craykon reads the line with Console.ReadLine().Trim(). The count table has 26 items, so Craykon's list limit does not matter, and strings go up to 10,000,000 characters, so 100,000 characters are fine.
Pythonmain.py · 34 lines
import syslines = sys.stdin.read().split()s, t = lines[0], lines[1]n = len(s)need = [0] * 26 # 글자마다 더 있어야 하는 수for ch in t: need[ord(ch) - 97] += 1missing = len(t) # 창 안에서 아직 모자란 구슬 수(모두 더한 것)best_start, best_len = -1, n + 1left = 0# 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다)for right in range(2 * n - 1): c = ord(s[right % n]) - 97 if need[c] > 0: missing -= 1 need[c] -= 1 if right - left + 1 > n: # 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 d = ord(s[left % n]) - 97 need[d] += 1 if need[d] > 0: missing += 1 left += 1 if missing == 0: # 왼쪽 끝 구슬이 남아도는 동안 줄인다 while need[ord(s[left % n]) - 97] < 0: need[ord(s[left % n]) - 97] += 1 left += 1 if left < n and right - left + 1 < best_len: # 같은 길이면 먼저 찾은(시작이 앞선) 것 best_start, best_len = left, right - left + 1print(f"{best_start + 1} {best_len}" if best_start >= 0 else -1)
JavaScriptmain.js · 27 lines
const [s, t] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i) => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need = new Array(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
TypeScriptmain.ts · 29 lines
import { readFileSync } from "node:fs";const [s, t] = readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i: number): number => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need: number[] = new Array<number>(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
JavaMain.java · 41 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); String t = in.readLine().trim(); int n = s.length(); int[] need = new int[26]; // 글자마다 더 있어야 하는 수 for (char ch : t.toCharArray()) need[ch - 'a']++; int missing = t.length(); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s.charAt(right % n) - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = s.charAt(left % n) - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s.charAt(left % n) - 'a'] < 0) { // 왼쪽 끝 구슬이 남아도는 동안 줄인다 need[s.charAt(left % n) - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } System.out.println(bestStart >= 0 ? (bestStart + 1) + " " + bestLen : "-1"); }}
C#Main.cs · 45 lines
using System;class Program{ static void Main() { string s = Console.ReadLine().Trim(); string t = Console.ReadLine().Trim(); int n = s.Length; var need = new int[26]; // 글자마다 더 있어야 하는 수 foreach (char ch in t) need[ch - 'a']++; int missing = t.Length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 { int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) // 왼쪽 끝 구슬이 남아도는 동안 줄인다 { need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) // 같은 길이면 먼저 찾은(시작이 앞선) 것 { bestStart = left; bestLen = right - left + 1; } } } Console.WriteLine(bestStart >= 0 ? $"{bestStart + 1} {bestLen}" : "-1"); }}
C++main.cpp · 37 lines
#include <array>#include <iostream>#include <string>int main() { std::string s, t; std::cin >> s >> t; const int n = static_cast<int>(s.size()); auto code = [&](int i) { return s[i % n] - 'a'; }; // 두 바퀴 붙인 줄의 i번째 구슬(0~25) std::array<int, 26> need{}; // 글자마다 더 있어야 하는 수 for (char ch : t) need[ch - 'a']++; int missing = static_cast<int>(t.size()); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; for (int right = 0; right < 2 * n - 1; right++) { int c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = code(left++); if (++need[d] > 0) missing++; } if (missing == 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } if (bestStart >= 0) std::cout << bestStart + 1 << " " << bestLen << "\n"; else std::cout << -1 << "\n";}
Cmain.c · 44 lines
#include <stdio.h>#include <string.h>#define MAXL 100000static char s[MAXL + 2], t[MAXL + 2];int main(void) { scanf("%100001s %100001s", s, t); int n = (int)strlen(s), k = (int)strlen(t); int need[26] = {0}; /* 글자마다 더 있어야 하는 수 */ for (int i = 0; i < k; i++) need[t[i] - 'a']++; int missing = k; /* 창 안에서 아직 모자란 구슬 수(모두 더한 것) */ int best_start = -1, best_len = n + 1; int left = 0; /* 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) */ for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { /* 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 */ int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) { /* 왼쪽 끝 구슬이 남아도는 동안 줄인다 */ need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < best_len) { /* 같은 길이면 먼저 찾은(시작이 앞선) 것 */ best_start = left; best_len = right - left + 1; } } } if (best_start >= 0) printf("%d %d\n", best_start + 1, best_len); else puts("-1"); return 0;}
Craykonmain.cray · 60 lines
// 두 바퀴 붙인 줄의 i번째 구슬을 0~25 번호로구슬(s, i){ return Str.Code(s[i % s.Length]) - 97;}s = Console.ReadLine().Trim();t = Console.ReadLine().Trim();n = s.Length;need = NewList(26, 0); // 글자마다 더 있어야 하는 수foreach (ch in t){ need[Str.Code(ch) - 97] += 1;}missing = t.Length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)bestStart = -1;bestLen = n + 1;left = 0;for (right = 0; right < 2 * n - 1; right++){ c = 구슬(s, right); if (need[c] > 0) { missing -= 1; } need[c] -= 1; if (right - left + 1 > n) { d = 구슬(s, left); left += 1; need[d] += 1; if (need[d] > 0) { missing += 1; } } if (missing == 0) { while (need[구슬(s, left)] < 0) { need[구슬(s, left)] += 1; left += 1; } if (left < n && right - left + 1 < bestLen) { bestStart = left; bestLen = right - left + 1; } }}if (bestStart >= 0){ Console.WriteLine(bestStart + 1 + " " + bestLen);}else{ Console.WriteLine(-1);}