|
||||
Title: interesting string problems Post by m_aakash on Mar 22nd, 2008, 12:18pm 1) Given s string, rearrange characters to form a longest palindrome. If multiple palindromes are possible, return first one in lexicographic order. If no palindrome can be formed then return NULL. 2) Describe an efficient algorithm to find the length of the longest substring that appears both forward and backward in an input string T[1 . n]. The forward and backward must not overlap. Ex: redivide output: 3 (edi) |
||||
Title: Re: interesting string problems Post by Grimbal on Mar 22nd, 2008, 4:09pm 1) Order all characters in ascending order. You have a sequence of characters, some repeated. Build the palindrome from the ends while scanning the sorted string from left to right. I.e. start with strings S and E, both empty. For every repeated character, add half of them at the end of S and another half to the front of S. Round the halves down. If any character is left (for an odd number) store the first one you meet as F. When done with the sorted string, your palindrome is S+F+E. |
||||
Title: Re: interesting string problems Post by m_aakash on Mar 22nd, 2008, 8:36pm on 03/22/08 at 16:09:02, Grimbal wrote:
well done grimbal... can you think of O(n^2) algo for second problem... i think we have to use dp for second one. |
||||
Title: Re: interesting string problems Post by Leo on Mar 22nd, 2008, 8:48pm (b) How about finding the longest common substring of the string and its reverse with an extra condition to check for overlap ... something like If S is the String and S' is its reverse. Then the LCS that comes up should be tested for length(S) - start_index(S') - start_index(S) - (2 * lendth(LCS)) > 0 would this work? ::) |
||||
Title: Re: interesting string problems Post by m_aakash on Mar 22nd, 2008, 9:48pm on 03/22/08 at 20:48:27, Leo wrote:
ex: fghqaaaaphgf Longest common substring is aaaa say your test detects overlap even then how do you find the actual result which is fgh |
||||
Title: Re: interesting string problems Post by pscoe2 on Mar 22nd, 2008, 10:23pm we can do as Leo suggested just keeping an array with tags which increment if they are counted for LCS Ex: fghqaaaaphgr 000022220000 bcoz this part has been considered for LCS twice for both S and S' in such a situation LCS can be either equal to half (or as the case might be...see the first starting 1 n the ending 1 and take mean) In the above case LCS=4/2=2 but as there are repetitions we hv to run the algo again just this time forbidding the LCS to come out to be the same do this till u get an LCS with all 0's and 1's and the find the longest of them Ex(contd.) in second iteration the array become 111000000111 which gives the value of LCS=3 and we see tht in the second case the LCS is higher and also there are only 0's and 1's in the final array so no more iterations are req. to get the optimal soln.s |
||||
Title: Re: interesting string problems Post by Leo on Mar 23rd, 2008, 12:09am here's an implementation in java ... [hide] String s = "fghqaaaaphgf"; String bestMatch = ""; String ss = Reverse(s); for (i=0;i<s.length();i++) { for (int k=ss.length()-1;k>=i+2;k--) { String subString = s.substring(i, k); int index = ss.indexOf(subString); if (index != -1) { //test for overlap here if ((s.length() - index) - i - (2 * (k - i)) > 0) { if (bestMatch.length() < subString.length()) bestMatch = subString; break; } } } } [/hide] |
||||
Title: Re: interesting string problems Post by Jigsaw on Jun 18th, 2008, 4:22am on 03/22/08 at 12:18:00, m_aakash wrote:
int n=str.size()-1; //1 based string for(int i=1;i<=n;i++) for(int j=n;j>i;j++) ls[i][j]=((str[i]==str[j])?ls[i-1][j+1]+1:0); The code is self explanatory I guess. The longest substring ending at i-1 from one direction and at j+1 from other direction can be extended by 1 if a[i] and b[j] are equal. Once you calculate the lcs matrix, if ls[i][j] contains the largest value, i gives the position in string and ls[i][j] gives the length of the substring which has the stated properties. [edit: replaced all lcs with ls] |
||||
Title: Re: interesting string problems Post by curt_cobain on Jun 21st, 2008, 12:14am 1) Order all characters in ascending order. You have a sequence of characters, some repeated. Build the palindrome from the ends while scanning the sorted string from left to right. I.e. start with strings S and E, both empty. For every repeated character, add half of them at the end of S and another half to the front of S. Round the halves down. If any character is left (for an odd number) store the first one you meet as F. When done with the sorted string, your palindrome is S+F+E. [hide][/hide] CAN U TELL ME WHAT IS IN E ALSO CAN U ELABORATE UR LOGIC WITH THE EAXAMPLE |
||||
Title: Re: interesting string problems Post by tuxilogy on Jun 23rd, 2008, 1:33am @ Jigsaw, Can you please xplain your LCS matrix logic, i could not get it |
||||
Title: Re: interesting string problems Post by Jigsaw on Jun 23rd, 2008, 9:02am on 06/23/08 at 01:33:35, tuxilogy wrote:
Yeah, sure. Say str[i-k. . .i-1] and rev(str[j+1. . .k+j]) are equal(i.e. has the desired property) and str[i-k...i-1] is the longest substring(as asked) ending at i-1 and is of length k, then the length of the longest substring ending at i is of length k+1 if str[i] == str[j]. Otherwise it(ls[i][j]) would be of length 0. E.g.: str=xyzzy ls[2][5]=1 (str[2](y)==str[5](y)) ls[3][4]=ls[2][5]+1=2 since str[3](z)==str[4](z) and ls[3][5]=0 since str[3](z)!=str[5](y) After constructing the whole matrix, find the indices i and j such that ls[i][j] is maximum. i is the position where the required substring ends and ls[i][j] is its length. Here comes the code(I've just coded and tested) Code:
[edit: replaced all lcs with "ls"] |
||||
Title: Re: interesting string problems Post by manita23 on Jul 22nd, 2014, 9:54pm Here is java method to find longest Palindrome string[] public static String longestPalindromeString(String s) { if (s == null) return null; String longest = s.substring(0, 1); for (int i = 0; i < s.length() - 1; i++) { //odd cases like 121 String palindrome = intermediatePalindrome(s, i, i); if (palindrome.length() > longest.length()) { longest = palindrome; } //even cases like 1221 palindrome = intermediatePalindrome(s, i, i + 1); if (palindrome.length() > longest.length()) { longest = palindrome; } } return longest; } |
||||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |