LEXOPAL - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, String

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
  3. 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.

2

authors solution link not working

3

Could someone explain why the time complexity is O(N) ? I am new to this concept of complexities.

4

A simple way to re-phrase the loop:

int front=0, end=input.length-1;
for(; front<end; front++, end--){ ... }
5

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