Given two strings of
lowercase letters a and b. Print the longest string x that is simultaneously a substring of
permutation of a and a substring of
permutation of b.
Input. Consists of multiple test cases, each contains a pair of
lines. The first line of a pair contains a
and the second line contains b. Each
string lies on a separate line and consists of at most 1000 lowercase letters.
Output. For each consecutive pair
of input lines print a line containing x.
If several x satisfy the criteria
above, choose the first one in alphabetical order.
Sample
input |
Sample
output |
pretty women walking down the
street |
e nw et |
data structures - map
Algorithm analysis
Count the number of each
letter that occurs in a and b. Find the number and type of
characters that simultaneously belong to lines a and b. Print them in
alphabetical order.
Algorithm realization
Read the input strings
into arrays a and b. In maps aa and bb we shall count
how many and what letters are contained in a
and b.
char a[1010], b[1010];
map<char,int> aa, bb;
For each test case read
input strings a and b. Fill the maps aa and bb.
while(gets(a))
{
gets(b);
aa.clear(); bb.clear();
for(i = 0; i
< strlen(a); i++) aa[a[i]]++;
for(i = 0; i
< strlen(b); i++) bb[b[i]]++;
Print the common letters of strings a and b in
alphabetical order. Print each letter as many times as it occurs simultaneously
in a and b.
for(i = 'a'; i <= 'z';
i++)
{
m = min(aa[i],bb[i]);
for(j = 0;
j < m; j++) printf("%c",i);
}
printf("\n");
}
Java realization
import
java.util.*;
public class
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
while(con.hasNext())
{
String a = con.nextLine();
String b = con.nextLine();
int aa[] = new int[256];
int bb[] = new int[256];
for(int i = 0; i < a.length(); i++)
aa[a.charAt(i)]++;
for(int i = 0; i < b.length(); i++)
bb[b.charAt(i)]++;
for(int i = 'a'; i <= 'z'; i++)
{
int m = Math.min(aa[i],bb[i]);
for(int j = 0; j < m; j++) System.out.print((char)i);
}
System.out.println();
}
}
}