SUBANAGRAMS

• Problem Description

  
  Strings A and B are called anagrams if its possible to rearrange the letters of string A using all the original letters exactly once and achieve string B; in other words A and B are permutations of each other. For example, remote and meteor are anagrams, race and race are anagrams as well, while seat and tease arent anagrams as tease contains an extra e.
  
  String A is called a subsequence of string B if A can be obtained from B by removing some (possibly none) characters. For example, cat is a subsequence of scratch, rage is a subsequence of rage, and tame is not a subsequence of steam.
  
  String A is lexicographically smaller than string B of the same length if at the first position where A and B differ A contains a letter which is earlier in the alphabet than the corresponding letter in B.
  
  Recently, Ann received a set of strings consisting of small Latin letters a..z. What can I do with them? -- she asked herself. What if I try to find the longest string which is a subsequence of every string from the set?. Ann spent a lot of time trying to solve the problem... but all her attempts happened to be unsuccessful. She then decided to allow the sought string to be an anagram of some subsequence of every string from the set. This problem seemed to be easier to Ann, but she was too tired to solve it, so Ann asked for your help.
  
  So your task is, given a set of strings, to find the longest non-empty string which satisfies Ann. Moreover, if there are many such strings, choose the lexicographically smallest one.
  Input
  
  The first line of the input file contains one integer N -- the number of strings in the set (1 <= N <= 100). Each of the next N lines contains a non-empty string consisting only of small Latin letters a..z representing a string from the set. None of the strings contain more than 100 letters.
  Output
  
  Output the longest non-empty string satisfying Ann. If there are several such strings, output the lexicographically smallest one. If there are no such strings, output no such string (quotes for clarity).
  Example
  
  Input:
  3
  hope
  elephant
  path
  
  Output:
  hp
  
  Input:
  2
  wall
  step
  
  Output:
  no such string
  
  Explanation:
  
  In the first test case the longest string appears to be two characters long. String hp satisfies the requirements as its an anagram of hp which is a subsequence of hope and an anagram of ph which is a subsequence of both elephant and path. Note that string ph also satisfies the requirements, but hp is lexicographically smaller.
  
  In the second test case there is no such string.

• CODING ARENA

• #include <stdio.h>

  int num[26], ans[26];

  char s[105];

  int min(int a, int b)

  {

    if(a<b)

      return a;

    return b;

  }

  int main()

  {

    int n,i,j,found;

    scanf("%d",&n);

    for(i=0;i<26;i++)

      ans[i]=101;

    for(j=0;j<n;j++)

    {

      scanf("%s",s);

      for(i=0;i<26;i++)

        num[i]=0;

      for(i=0;s[i]!='\0';i++)

        num[s[i]-'a']++;

      for(i=0;i<26;i++)

        ans[i]=min(ans[i],num[i]);

    }

    found=0;

    for(i=0;i<26;i++)

      {

        for(j=0;j<ans[i];j++)

        {

          printf("%c",i+'a');

          found=1;

        }

      }

    if(!found)

        printf("no such string");

   

  return 0;

  }

• Test Case 1

  
  Input (stdin)

  3
  
  hope
  
  elephant
  
  path
  
  

  Expected Output

  hp

• Test Case 2

  
  Input (stdin)

  2
  
  wall
  
  step
  
  

  Expected Output

  no such string