wu :: forums
« wu :: forums - interesting string problems »

Welcome, Guest. Please Login or Register.
May 19th, 2024, 9:41am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: william wu, Eigenray, towr, ThudnBlunder, SMQ, Icarus, Grimbal)
   interesting string problems
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: interesting string problems  (Read 7308 times)
m_aakash
Junior Member
**





   


Posts: 96
interesting string problems  
« on: Mar 22nd, 2008, 12:18pm »
Quote Quote Modify Modify

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)
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7527
Re: interesting string problems  
« Reply #1 on: Mar 22nd, 2008, 4:09pm »
Quote Quote Modify Modify

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.
IP Logged
m_aakash
Junior Member
**





   


Posts: 96
Re: interesting string problems  
« Reply #2 on: Mar 22nd, 2008, 8:36pm »
Quote Quote Modify Modify

on Mar 22nd, 2008, 4:09pm, Grimbal wrote:
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.

 
well done grimbal...
 
can you think of O(n^2) algo for second problem...
i think we have to use dp for second one.
IP Logged
Leo
Newbie
*





  rkoushik84  
WWW

Gender: male
Posts: 8
Re: interesting string problems  
« Reply #3 on: Mar 22nd, 2008, 8:48pm »
Quote Quote Modify Modify

(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?  Roll Eyes
IP Logged
m_aakash
Junior Member
**





   


Posts: 96
Re: interesting string problems  
« Reply #4 on: Mar 22nd, 2008, 9:48pm »
Quote Quote Modify Modify

on Mar 22nd, 2008, 8:48pm, Leo wrote:
(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?  Roll Eyes

 
ex: fghqaaaaphgf
Longest common substring is aaaa
say your test detects overlap even then how do you find the actual result which is fgh
IP Logged
pscoe2
Junior Member
**





   


Gender: male
Posts: 77
Re: interesting string problems  
« Reply #5 on: Mar 22nd, 2008, 10:23pm »
Quote Quote Modify Modify

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
« Last Edit: Mar 22nd, 2008, 10:28pm by pscoe2 » IP Logged
Leo
Newbie
*





  rkoushik84  
WWW

Gender: male
Posts: 8
Re: interesting string problems  
« Reply #6 on: Mar 23rd, 2008, 12:09am »
Quote Quote Modify Modify

here's an implementation in java ...  

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;
   }
  }
 }
}

 
IP Logged
Jigsaw
Guest

Email

Re: interesting string problems  
« Reply #7 on: Jun 18th, 2008, 4:22am »
Quote Quote Modify Modify Remove Remove

on Mar 22nd, 2008, 12:18pm, m_aakash wrote:
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)

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]
« Last Edit: Jun 23rd, 2008, 9:05am by jagatsastry » IP Logged
curt_cobain
Newbie
*





   


Posts: 33
Re: interesting string problems  
« Reply #8 on: Jun 21st, 2008, 12:14am »
Quote Quote Modify Modify

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
IP Logged
tuxilogy
Newbie
*





   


Posts: 45
Re: interesting string problems  
« Reply #9 on: Jun 23rd, 2008, 1:33am »
Quote Quote Modify Modify

@ Jigsaw,  
 
Can you please xplain your LCS matrix logic, i could not get it
IP Logged
Jigsaw
Guest

Email

Re: interesting string problems  
« Reply #10 on: Jun 23rd, 2008, 9:02am »
Quote Quote Modify Modify Remove Remove

on Jun 23rd, 2008, 1:33am, tuxilogy wrote:
@ Jigsaw,  
 
Can you please xplain your LCS matrix logic, i could not get it

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:

string getLcs(const string& str)
{
 int n=str.size();
 vector<vector<int> > ls(n+2, vector<int>(n+2,0));
 
 pair<int, int> max(0, -1); //Max value, index
 for(int i=1;i<=n;i++)
  for(int j=n;j>i;j--)
    {
        ls[i][j]=(str[i-1]==str[j-1])?ls[i-1][j+1]+1:0; //Indices adjusted for 0 based string indices
        if(ls[i][j]>max.first)
        max.first=ls[i][j], max.second=i;
    }
 if(max.second==-1)
 return "";
 else return string(str, max.second-max.first, max.first);  
}
 

[edit: replaced all lcs with "ls"]
« Last Edit: Jun 23rd, 2008, 9:07am by jagatsastry » IP Logged
manita23
Newbie
*





   


Posts: 5
Re: interesting string problems  
« Reply #11 on: Jul 22nd, 2014, 9:54pm »
Quote Quote Modify Modify

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;
    }
 
« Last Edit: Aug 13th, 2014, 6:59am by Grimbal » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board