2040. Common permutation

 

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

 

 

SOLUTION

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 Main

{

  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();     

    }

  }

}