# Longest Non-palindromic substring

Given a string of size n. The task is to find the length of the largest substring which is not palindrome.

Examples:

Input : abba Output : 3 Here maximum length non-palindromic substring is 'abb' which is of length '3'. There could be other non-palindromic sub-strings also of length three like 'bba' in this case. Input : a Output : 0

A **simple solution **is to consider every substring and check if it is palindrome or not. Finally return length of the longest non-palindromic substring.

An **efficient solution** is based on below approach.

Check for the case where all characters of the string are same or not. If yes, then answer will be '0'. Else check whether the given string of size 'n' is palindrome or not. If yes, then answer will be 'n-1' Else answer will be 'n'

- C++

// C++ implementation to find maximum length // substring which is not palindrome #include <bits/stdc++.h> using namespace std; // utility function to check whether // a string is palindrome or not bool isPalindrome(string str) { // Check for palindrome. int n = str.size(); for (int i=0; i < n/2; i++) if (str.at(i) != str.at(n-i-1)) return false; // palindrome string return true; } // function to find maximum length // substring which is not palindrome int maxLengthNonPalinSubstring(string str) { int n = str.size(); char ch = str.at(0); // to check whether all characters // of the string are same or not int i = 1; for (i=1; i<n; i++) if (str.at(i) != ch) break; // All characters are same, we can't // make a non-palindromic string. if (i == n) return 0; // If string is palindrome, we can make // it non-palindrome by removing any // corner character if (isPalindrome(str)) return n-1; // Complete string is not a palindrome. return n; } // Driver program to test above int main() { string str = "abba"; cout << "Maximum length = " << maxLengthNonPalinSubstring(str); return 0; }

Output:

Maximum length = 3

Time Complexity: O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below

source and credits.

source and credits:http://www.geeksforgeeks.org/longest-non-palindromic-substring/

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon

If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements

#technicalguide