문자열 잘라내기

면접 대비

시간 제한1초메모리 제한256 MB

요약

표의 맨 위 행을 하나씩 제거하면서 각 열 문자열이 서로 다르게 유지되는 최대 제거 횟수를 구합니다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 문자열, 해시맵
정답자: 아직 제출이 없습니다

문제

R개의 행과 C개의 열로 이루어진 테이블이 주어진다. 각 칸에는 알파벳 소문자 하나가 들어 있다.

각 열을 위에서 아래로 읽으면 열마다 하나의 문자열을 만들 수 있다. 한 번의 작업은 현재 테이블의 가장 위 행을 지우는 것이다. 행을 지운 뒤에도 C개의 열 문자열이 모두 서로 다르면 실제로 그 행을 지우고 count를 1 증가시킨다. 행을 지운 뒤 같은 열 문자열이 두 개 이상 생기면 작업을 멈추고 count를 출력한다.

처음 주어지는 테이블은 열을 위에서 아래로 읽어 만든 문자열이 모두 서로 다르다. 최종 count 값을 구하자.

입력

첫 번째 줄에 테이블의 행 개수와 열 개수인 R과 C가 주어진다. (2 <= R, C <= 1000)

이후 R줄에 걸쳐 각 줄마다 C개의 알파벳 소문자가 주어진다. 처음 주어지는 테이블에서는 각 열을 위에서 아래로 읽어 만든 문자열이 모두 서로 다르다.

출력

위에서 설명한 count의 값을 출력한다.

예제3

예제 1
입력
```
2 6
dobarz
adatak
```
예상 출력
```
0
```
예제 2
입력
```
3 4
alfa
beta
zeta
```
예상 출력
```
2
```
예제 3
입력
```
4 6
mrvica
mrvica
marica
mateja
```
예상 출력
```
1
```