PROBLEM LINK:Author: Sunny Aggarwal DIFFICULTY:Easy PREREQUISITES:Adhoc, 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.
This question is marked "community wiki".
asked 15 Sep '16, 14:51

Could someone explain why the time complexity is O(N) ? I am new to this concept of complexities. answered 15 Sep '16, 20:24

A simple way to rephrase the loop:
answered 16 Sep '16, 12:30

My approach ::
answered 03 May '18, 14:55
