 # Same as SPOJ PALIN

#1
``````bool allNine(string s){
for(int i = 0; i < s.size(); ++i){
if(s[i] != '9')return false;
}
return true;
}
string Solution::solve(string s) {
int n = s.size();
if(allNine(s)){
s = '1';

for(int i = 1; i < n; ++i){
s[i] = '0';
}
s.push_back('1');
}
else{

// split: s = left + right
int i = n/2;
int j = i;
if(n%2 == 0)i--; // to work with even sized string

// find the point where they stop being palindrome
while(i >= 0 && s[i] == s[j]){
i--,j++;
}

// if s was already a plaindrome or left is smaller than right : go to middle and add carry of 1 and propagate it till it don't match and then simply copy the rest of left into right
if(i < 0 || s[i] < s[j]){
i = n/2;
j = i;
if(n%2 == 0)i--;
int carry = 1;
while(i >= 0){
int num = (s[i]-'0') + carry;
carry = num/10;
num %= 10;
s[i] = '0' + num;
s[j] = s[i];
i--, j++;
}
}
// if right is smaller than left, ans = left + reverse(left)
else{
i = n/2;
j = i;
if(n%2 == 0)i--;

while(i >= 0){
s[j] = s[i];
i--, j++;
}
}
}
return s;

}

``````

#2

Nice Solution. Short and simple