공통 순열
면접 대비시간 제한2초메모리 제한128 MB
두 문자열이 주어질 때 각 알파벳의 등장 횟수를 비교해 공통으로 사용할 수 있는 글자들을 모아 사전순으로 출력합니다.
문제
알파벳 소문자로 이루어진 두 문자열 a와 b가 주어진다. 문자열 x가 a의 부분 수열을 재배열한 문자열이면서 동시에 b의 부분 수열을 재배열한 문자열이 되도록 할 때, 가능한 x 중 길이가 가장 긴 문자열을 구하라.
입력
입력은 파일의 끝까지 여러 테스트 케이스로 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.
첫 번째 줄에 문자열 a, 두 번째 줄에 문자열 b가 주어진다.
각 문자열은 최대 1000개의 알파벳 소문자로 이루어진다.
출력
각 테스트 케이스마다 한 줄에 x를 출력한다.
가능한 가장 긴 x가 여러 개라면 사전순으로 가장 앞서는 문자열을 출력한다. 공통으로 고를 수 있는 문자가 없으면 빈 줄을 출력한다.