Longest double string from a Palindrome
Given a palindrome String, the task is to find the maximum length of the double string and its length that can be obtained from the given palindromic string. A double string is a string that has two clear repetition of a substring one after the other.
Examples:
Input: abba Output: abab 4 Explanation: abab is double string which can be obtained by changing the order of letters Input: abcba Output: abab 4 Explanation: abab is double string which can be obtained by changing the order of letters and deleting letter c
Approach: The double string can be considered in two cases:
- Case 1: If the length of the string is even then the length of double string will always be the length of string.
- Case 2: If the length of the string is odd then the length of double string will always be the length of string – 1.
Below is the implementation of the above approach
C++
#include <bits/stdc++.h> using namespace std; // Function to return the required position int lenDoubleString(string s) { int l = s.length(); string first_half = s.substr(0, l / 2); string second_half = "" ; if (l % 2 == 0) second_half = s.substr(l / 2); else second_half = s.substr(l / 2 + 1); reverse(second_half.begin(), second_half.end()); // Print the double string cout << first_half << second_half << endl; // Print the length of the double string if (l % 2 == 0) cout << l << endl; else cout << l - 1 << endl; } int main() { string n = "abba" ; lenDoubleString(n); n = "abcdedcba" ; lenDoubleString(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the required position static int lenDoubleString(String s) { int l = s.length(); String first_half = s.substring( 0 , l / 2 ); String second_half = "" ; if (l % 2 == 0 ) second_half = s.substring(l / 2 ); else second_half = s.substring(l / 2 + 1 ); second_half = reverse(second_half); // Print the double String System.out.println(first_half + second_half); // Print the length of the double String if (l % 2 == 0 ) System.out.println(l); else System.out.println(l - 1 ); return Integer.MIN_VALUE; } static String reverse(String input) { char [] temparray = input.toCharArray(); int left, right = 0 ; right = temparray.length - 1 ; for (left = 0 ; left < right; left++, right--) { // Swap values of left and right char temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return String.valueOf(temparray); } // Driver code public static void main(String[] args) { String n = "abba" ; lenDoubleString(n); n = "abcdedcba" ; lenDoubleString(n); } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach. # Function to return the required position def lenDoubleString(s): l = len (s) first_half = s[ 0 : l / / 2 ] second_half = "" if l % 2 = = 0 : second_half = s[l / / 2 : ] else : second_half = s[l / / 2 + 1 : ] second_half = second_half[:: - 1 ] # Print the double string print (first_half + second_half) # Print the length of the double string if l % 2 = = 0 : print (l) else : print (l - 1 ) # Driver Code if __name__ = = "__main__" : n = "abba" lenDoubleString(n) n = "abcdedcba" lenDoubleString(n) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System; class GFG { // Function to return the required position static int lenDoubleString(String s) { int l = s.Length; String first_half = s.Substring(0, l / 2); String second_half = "" ; if (l % 2 == 0) second_half = s.Substring(l / 2); else second_half = s.Substring(l / 2 + 1); second_half = reverse(second_half); // Print the double String Console.WriteLine(first_half + second_half); // Print the length of the double String if (l % 2 == 0) Console.WriteLine(l); else Console.WriteLine(l - 1); return int .MinValue; } static String reverse(String input) { char [] temparray = input.ToCharArray(); int left, right = 0; right = temparray.Length - 1; for (left = 0; left < right; left++, right--) { // Swap values of left and right char temp = temparray[left]; temparray[left] = temparray[right]; temparray[right] = temp; } return String.Join( "" ,temparray); } // Driver code public static void Main(String[] args) { String n = "abba" ; lenDoubleString(n); n = "abcdedcba" ; lenDoubleString(n); } } // This code has been contributed by 29AjayKumar |
PHP
<?php // PHP implementation of the approach // Function to return the required position function lenDoubleString( $s ) { $l = strlen ( $s ); $first_half = substr ( $s , 0, (int)( $l / 2)); $second_half = "" ; if ( $l % 2 == 0) $second_half = substr ( $s , (int)( $l / 2)); else $second_half = substr ( $s , (int)( $l / 2 + 1)); $second_half = strrev ( $second_half ); // Print the double string echo $first_half . "" . $second_half . "\n" ; // Print the length of the double string if ( $l % 2 == 0) echo $l . "\n" ; else echo ( $l - 1) . "\n" ; } // Driver Code $n = "abba" ; lenDoubleString( $n ); $n = "abcdedcba" ; lenDoubleString( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation of the // above approach // Function to return the required position function lenDoubleString(s) { var l = s.length; var first_half = s.substr(0, l / 2); var second_half = "" ; if (l % 2 == 0) second_half = s.substr(l / 2); else second_half = s.substr(l / 2 + 1); second_half = second_half.split( "" ).reverse().join( "" ); // Print the double string document.write(first_half); document.write(second_half+ "<br>" ); // Print the length of the double string if (l % 2 == 0) document.write(l+ "<br>" ); else document.write(l - 1+ "<br>" ); } var n = "abba" ; lenDoubleString(n); n = "abcdedcba" ; lenDoubleString(n); // This code is contributed by ShubhamSingh10 </script> |
Output:
abab 4 abcdabcd 8
Time Complexity: O(N), as we are using built-in functions reverse which will cost O(N) time.
Auxiliary Space: O(N), as we are using extra space.