## Monday, November 21, 2016

### Smallest Palindrome after replacement - GeeksforGeeks

Smallest Palindrome after replacement - GeeksforGeeks
Given a string which has some lowercase alphabet characters and one special character dot(.). We need to replace all dots with some alphabet character in such a way that resultant string becomes a palindrome, in case of many possible replacements, we need to choose palindrome string which is lexicographically smallest. If it is not possible to convert string into palindrome after all possible replacements then output Not possible.

```If both "i", and "n- i- 1" are dot, replace them by ‘a’
If one of them is a dot character replace that by other non-dot character```
`bool` `isPossiblePalindrome(string str)`
`{`
`    ``int` `n = str.length();`
`    ``for` `(``int` `i=0; i<n/2; i++)`
`    ``{`
`        ``/* If both left and right character are not`
`           ``dot and they are not equal also, then it`
`           ``is not possible to make this string a`
`           ``palindrome   */`
`        ``if` `(str[i] != ``'.'` `&&`
`            ``str[n-i-1] != ``'.'` `&&`
`            ``str[i] != str[n-i-1])`
`            ``return` `false``;`
`    ``}`

`    ``return` `true``;`
`}`

`// Returns lexicographically smallest palindrom`
`// string, if possible`
`string smallestPalindrome(string str)`
`{`
`    ``if` `(!isPossiblePalindrome(str))`
`        ``return` `"Not Possible"``;`

`    ``int` `n = str.length();`

`    ``//  loop through character of string`
`    ``for` `(``int` `i = 0; i < n; i++)`
`    ``{`
`        ``if` `(str[i] == ``'.'``)`
`        ``{`
`            ``// if one of character is dot, replace dot`
`            ``// with other character`
`            ``if` `(str[n - i - 1] != ``'.'``)`
`                ``str[i] = str[n - i - 1];`

`            ``// if both character are dot, then replace`
`            ``// them with smallest character 'a'`
`            ``else`
`                ``str[i] = str[n - i - 1] = ``'a'``;`
`        ``}`
`    ``}`

`    ``//  return the result`
`    ``return` `str;`
`}`