×

# LEXOPAL - Editorial

Author: Sunny Aggarwal
Tester: Praveen Dhinwa
Editorialist: Ajay K. Verma

Easy

# PROBLEM:

Given a string with Latin alphabets and a special character, find the lexicographically smallest palindrome string, which can be obtained by replacing each occurrence of the special character by a Latin alphabet, if possible, otherwise indicate that such string is impossible to construct.

# QUICK EXPLANATION:

Fill all the occurrences of the special characters using the information that the resulting string has to be a palindrome. Replace all the remaining occurrences of the special character by 'a'. If a palindrome string is possible to achieve, then this would the lexicographically smallest such string.

# EXPLANATION:

We are given a string S with latin alphabets and a special character dot (.). The goal is to transform this string into the lexicographically smallest palindrome string T by replacing all occurrences of special characters dot by some latin alphabet. In other words,

1) T[i] = S[i], if S[i] is a latin alphabet, 2) T[i] = T[n - 1 - i], where n is the length of the string, and 2) T is the lexicographically smallest string satisfying the above requirements.

If for some i, both S[i] and S[n - 1 - i] are latin alphabets, and they are not equal to each other, then T cannot be a palindrome string because

T[i] = S[i] != S[n - 1 - i] = T[n - 1 - i] T[i] != T[n - 1 - i]

Hence, we should discard such string immediately.

On the other hand, if exactly one of the S[i] and S[n - 1 - i] is a latin alphabet x, and the other one is the special character, then in the string T, the special character must be the same as the latin alphabet x.

The only case remains when both S[i] and S[n - 1 - i] are special characters. In this case we need to replace both S[i] and S[n - 1 - i] by the same character x in T. Any choice of x would result in a palindrome string, however, since we are looking for the smallest palindrome string, the x should be 'a'.

void MakePalindrome(string S) {
int n = S.size();
for (int i = 0; i <= n - 1 - i; ++i) {
if (S[i] != '.'  && S[n - 1 - i] != '.') {
if (S[i] != S[n - 1 - i]) {
print(-1);
return;
}
continue;
}

if (S[i] == '.' && S[n - 1 - i] == '.') {
S[i] = S[n - 1 - i] = 'a';
continue;
}

if (S[i] == '.')
S[i] = S[n - 1 - i];
else
S[n - 1 - i] = S[i];
}
print(S);


# TIME COMPLEXITY:

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

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be uploaded soon.
Tester's solution will be uploaded soon.

This question is marked "community wiki".

6★djdolls
2.2k518484
accept rate: 0%

19.8k350498541

 0 authors solution link not working answered 15 Sep '16, 16:21 1.2k●12 accept rate: 18%
 0 Could someone explain why the time complexity is O(N) ? I am new to this concept of complexities. answered 15 Sep '16, 20:24 3●1 accept rate: 0%
 0 A simple way to re-phrase the loop: int front=0, end=input.length-1; for(; front
 0 My approach :: for __ in range(readInt()): s=readStr() l=list(s) F=True for i in range(len(s)): # print "l[i]",l[i],l[-1-i] if l[i]==".": if l[i]==l[-i-1]: l[i],l[-1-i]="a","a" continue else: l[i]=l[-i-1] elif l[-1-i]==".": if l[i]==l[-i-1]: l[i],l[-1-i]="a","a" continue else: l[-i-1]=l[i] else: if l[i]!=l[-i-1]: F=False break if F: print strlistTostr(l) else: print -1  answered 03 May '18, 14:55 318●1●10 accept rate: 1%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,719
×3,770
×952
×644
×129
×5

question asked: 15 Sep '16, 14:51

question was seen: 3,000 times

last updated: 03 May '18, 14:55