Mirror String

Easy

0/40

Average time to solve is 15m

30 upvotes

Asked in companies

Problem statement

You are given a string S containing only uppercase English characters. Find whether S is the same as its reflection in the mirror.

For Example, S = “AMAMA” is the same as its reflection in the mirror.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer T, denoting the number of test cases.

The first line of each test case contains a string 'S'.

Output Format:

For each test case, print a single line containing “YES” or “NO” depending on whether the string 'S' is the same as its reflection in the mirror or not.

The output of each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the function.

The return type of the function is boolean, which returns true if the string is the same as its reflection in the mirror, otherwise returns false.

Constraints

1 <= T <=10
1 <= Length(S) <= 10 ^ 5

Where ‘T’ is the number of test cases, ‘S’ is the string given in input.

Time limit: 1sec.

Sample Input 1:

1
ITATI

Sample Output 1:

YES

Explanation of sample input 1:

String “ITATI” is the same as its reflection in the mirror.

Sample Input 2:

2
MMMM
MZM

Sample Output 2:

YES
NO

Hint 1

Check for symmetricity of the characters of the string.

Approaches (1)

Approach 1

Check Palindrome and Symmetricity

For a string to be same as its reflection in the mirror, it should satisfy the following conditions:

The given string “S” needs to be a palindrome.
All the characters of the string must be symmetric so that the reflection of the characters remains the same.

The symmetric characters are AHIMOTUVWXY.
Store the symmetric characters in an unordered set, traverse the string, and if the string contains any non-symmetric character, then return false.
If all the characters present in the string are symmetric, then check if the string is a palindrome or not. If the string is a palindrome, then return true, otherwise, return false.

Time Complexity

O(N), where N is the length of the string.

Finding an element in an unordered set takes constant time, O(1) on average. Thus, traversing the string to check for symmetric characters takes O(N * 1) = O(N) time.
Checking whether the string is a palindrome or not also takes linear time, O(N)

So, the final time complexity is O(N + N) = O(N).

Space Complexity

O(1).

Only constant additional space is required to store the symmetric characters.

(100% EXP penalty)

Mirror String

Console