You are not logged in. Please login at www.codechef.com to post your questions!

×

SUBANAGR - Editorial

4
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

It's easy to check if a string is an anagram or a subsequence of some other string. Is it easy to check if a string is an anagram of some subsequence (a subanagram) of some other string? Yes, it is!

To see that, notice that if string A contains more letters 'a' than string B, then A can't be a subanagram of B. The same is the case for any other letter. If no such letters exist, it's obvious that A is a subanagram of B -- we may remove extra letters from B to get A's anagram.

When we're dealing with a set of strings, it's easy to see that each letter's quantity in the resulting string can't exceed the corresponding quantity in each string from the set. As we need the longest possible string, let's set each letter's quantity to be equal to the smallest of such quantities in the strings of the set. Lastly, as we need the lexicographically smallest string, output the resulting letters in alphabetical order as their order doesn't matter.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 22 Nov '12, 17:41

admin's gravatar image

0★admin ♦♦
19.1k348495534
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,850
×3,291
×6
×4

question asked: 22 Nov '12, 17:41

question was seen: 2,408 times

last updated: 22 Nov '12, 17:41