시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 10 10 43.478%

문제

상근이의 키보드가 망가졌다. 키보드의 일부 키는 작동을 해서 아직 입력을 할 수 있다. 상근이는 키보드의 레이아웃을 바꿔서 단어를 입력하려고 한다. 지금 키보드에서 작동하는 키의 개수는 m개이다.

상근이가 입력하려고 하는 문장이 주어졌을 때, 키보드의 레이아웃을 바꾸지 않고 입력할 수 있는 연속하는 문자의 최대값을 구하는 프로그램을 작성하시오. 키보드의 한 키는 문자 하나에 매핑되고, 다른 키와 조합을 이용해서 문자를 입력할 수는 없다. 즉, 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열을 찾으면 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는 문장이 주어진다. 이 문장은 백만글자를 넘지 않으며, 공백을 포함할 수 있다. 공백도 문자로 생각하고 문제를 풀어야 한다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 최대 m개의 서로 다른 문자로 이루어진 가장 긴 부분 문자열의 길이를 출력한다.

예제 입력 1

5
This can't be solved by brute force.
1
Mississippi
0

예제 출력 1

7
2
W3sicHJvYmxlbV9pZCI6IjY1MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZGRcdWFjMDBcdWM5YzQgXHVkMGE0XHViY2Y0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVkMGE0XHViY2Y0XHViNGRjXHVhYzAwIFx1YjlkZFx1YWMwMFx1Yzg0Y1x1YjJlNC4gXHVkMGE0XHViY2Y0XHViNGRjXHVjNzU4IFx1Yzc3Y1x1YmQ4MCBcdWQwYTRcdWIyOTQgXHVjNzkxXHViM2Q5XHVjNzQ0IFx1ZDU3NFx1YzExYyBcdWM1NDRcdWM5YzEgXHVjNzg1XHViODI1XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkMGE0XHViY2Y0XHViNGRjXHVjNzU4IFx1YjgwOFx1Yzc3NFx1YzU0NFx1YzZjM1x1Yzc0NCBcdWJjMTRcdWFmZDRcdWMxMWMgXHViMmU4XHVjNWI0XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzljMFx1YWUwOCBcdWQwYTRcdWJjZjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjNzkxXHViM2Q5XHVkNTU4XHViMjk0IFx1ZDBhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgbVx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViYjM4XHVjN2E1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDBhNFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWI4MDhcdWM3NzRcdWM1NDRcdWM2YzNcdWM3NDQgXHViYzE0XHVhZmI4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM3ODVcdWI4MjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWMxOGRcdWQ1NThcdWIyOTQgXHViYjM4XHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkMGE0XHViY2Y0XHViNGRjXHVjNzU4IFx1ZDU1YyBcdWQwYTRcdWIyOTQgXHViYjM4XHVjNzkwIFx1ZDU1OFx1YjA5OFx1YzVkMCBcdWI5ZTRcdWQ1NTFcdWI0MThcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWQwYTRcdWM2NDAgXHVjODcwXHVkNTY5XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjNzg1XHViODI1XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVjZDVjXHViMzAwIG1cdWFjMWNcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWM3M2NcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBtICZsZTsgMTI4KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1YzdhNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3YTVcdWM3NDAgXHViYzMxXHViOWNjXHVhZTAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhY2Y1XHViYzMxXHViM2M0IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWFjZTAgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkmbmJzcDtcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWNkNWNcdWIzMDAgbVx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjUwMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJyb2tlbiBLZXlib2FyZCIsImRlc2NyaXB0aW9uIjoiPHA+QnJ1Y2UgRm9yY2UmIzM5O3Mga2V5Ym9hcmQgaXMgYnJva2VuLCBvbmx5IGEgZmV3IGtleXMgYXJlIHN0aWxsIHdvcmtpbmcuIEJydWNlIGhhcyBmaWd1cmVkIG91dCBoZSBjYW4gc3RpbGwgdHlwZSB0ZXh0cyBieSBzd2l0Y2hpbmcgdGhlIGtleWJvYXJkIGxheW91dCB3aGVuZXZlciBoZSBuZWVkcyB0byB0eXBlIGEgbGV0dGVyIHdoaWNoIGlzIGN1cnJlbnRseSBub3QgbWFwcGVkIHRvIGFueSBvZiB0aGUgbSB3b3JraW5nIGtleXMgb2YgdGhlIGtleWJvYXJkLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIGEgdGV4dCB0aGF0IEJydWNlIHdpc2hlcyB0byB0eXBlLCBhbmQgaGUgYXNrcyB5b3UgaWYgeW91IGNhbiB0ZWxsIGhpbSB0aGUgbWF4aW11bSBudW1iZXIgb2YgY29uc2VjdXRpdmUgY2hhcmFjdGVycyBpbiB0aGUgdGV4dCB3aGljaCBjYW4gYmUgdHlwZWQgd2l0aG91dCBoYXZpbmcgdG8gc3dpdGNoIHRoZSBrZXlib2FyZCBsYXlvdXQuIEZvciBzaW1wbGljaXR5LCB3ZSBhc3N1bWUgdGhhdCBlYWNoIGtleSBvZiB0aGUga2V5Ym9hcmQgd2lsbCBiZSBtYXBwZWQgdG8gZXhhY3RseSBvbmUgY2hhcmFjdGVyLCBhbmQgaXQgaXMgbm90IHBvc3NpYmxlIHRvIHR5cGUgb3RoZXIgY2hhcmFjdGVycyBieSBjb21iaW5hdGlvbiBvZiBkaWZmZXJlbnQga2V5cy4gVGhpcyBtZWFucyB0aGF0IEJydWNlIHdhbnRzIHRvIGtub3cgdGhlIGxlbmd0aCBvZiB0aGUgbGFyZ2VzdCBzdWJzdHJpbmcgb2YgdGhlIHRleHQgd2hpY2ggY29uc2lzdHMgb2YgYXQgbW9zdCBtIGRpZmZlcmVudCBjaGFyYWN0ZXJzPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLCBlYWNoIHRlc3QgY2FzZSBjb25zaXN0aW5nIG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29udGFpbnMgdGhlIG51bWJlciBtICgxICZsZTsgbSAmbGU7IDEyOCksIHdoaWNoIHNwZWNpZmllcyBob3cgbWFueSBrZXlzIG9uIHRoZSBrZXlib2FyZCBhcmUgc3RpbGwgd29ya2luZy4gVGhlIHNlY29uZCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIHRoZSB0ZXh0IHdoaWNoIEJydWNlIHdhbnRzIHRvIHR5cGUuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGxlbmd0aCBvZiB0aGlzIHRleHQgZG9lcyBub3QgZXhjZWVkIDEgbWlsbGlvbiBjaGFyYWN0ZXJzLiBOb3RlIHRoYXQgdGhlIGlucHV0IG1heSBjb250YWluIHNwYWNlIGNoYXJhY3RlcnMsIHdoaWNoIHNob3VsZCBiZSBoYW5kbGVkIGxpa2UgYW55IG90aGVyIGNoYXJhY3Rlci48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIG9uZSB6ZXJvPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZSB3aXRoIHRoZSBsZW5ndGggb2YgdGhlIGxhcmdlc3Qgc3Vic3RyaW5nIG9mIHRoZSB0ZXh0IHdoaWNoIGNvbnNpc3RzIG9mIGF0IG1vc3QgbSBkaWZmZXJlbnQgY2hhcmFjdGVyczxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2008 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: satuboy