All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Lexicographically minimal string

Arrays and Strings, Data Structures, Disjoint Data Structures, Disjoint Set, Disjoint set, Graphs


You are given three strings named as \(A\)\(B\), and \(C\). Here, the length of the strings \(A\) and \(B\)  is equal. All strings contain lowercase English letters. The string \(A\) and \(B\) contain the following properties:

  1. The characters located at the same indexes in the string \(A\)  and \(B\) are equivalent to each other. 
  2. If character \(a\) is equivalent to character \(b\) , then the character \(b\) is also equivalent to the character \(a\).
  3. If character \(a\) is equivalent to character \(b\) and character \(b\) is equivalent to character \(c \), then character \(a\) is also equivalent to character \(c \).
  4. Every character is equivalent to itself.

For example:

You are given two strings:

  • \(A - abc\)  
  • \(B - xcd\)

Here, the character \(a\) is equivalent to the character \(x \), character \(b\) is equivalent to the character \(c \), and character \(c \) is equivalent to the character \(d\). According to the third property, the character \(b\) is also equivalent to the character \(d\).

You can replace any character of string \(C\) with its any equivalent character. By replacing any character of the string \(C\) with its equivalent characters, you can construct multiple new strings. Your task is to print the lexicographically smallest string out of all possible new strings that you can construct.

Note: If the first character of \(s(s_1)\) is smaller than the first character of \(t(t_1)\), then the lexicographical order is an order relation where string \(s\) is smaller than string \(t\). If they are equivalent, the second character is checked and so on.

Input format

  • First line: String \(A\) 
  • Second line: String \(B\)
  • Third line: String \(C\)

Output format

Print the lexicographically smallest string. 


 \(1\leq\) length of strings \(A,B,C \leq 100000\)

length of string \(A\) = length of string \(B\)

All the strings consist of lowercase English letters.


In string \(C\) , you can replace \(y\) with \(b\) and \(z\) with \(c\) to find the lexicographically smallest string.

From string \(A\) and \(B\),

\(a\) is equivalent to \(x\)

\(b\) is equivalent to \(y\)

\(c\) is equivalent to \(z\)

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications