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

×

LEXOPAL - Editorial

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

asked 15 Sep '16, 14:51

djdolls's gravatar image

6★djdolls
2.2k518484
accept rate: 0%

edited 16 Sep '16, 12:59

admin's gravatar image

0★admin ♦♦
19.8k350498541


authors solution link not working

link

answered 15 Sep '16, 16:21

acodebreaker2's gravatar image

1★acodebreaker2
1.2k12
accept rate: 18%

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

link

answered 15 Sep '16, 20:24

revanth_97's gravatar image

2★revanth_97
31
accept rate: 0%

A simple way to re-phrase the loop:

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

answered 16 Sep '16, 12:30

amitg87's gravatar image

2★amitg87
11
accept rate: 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
link

answered 03 May '18, 14:55

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

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:

×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