Max length of substring-palindrome

  • C/C++
  • Thread starter member 428835
  • Start date
  • Tags
    Length Max
In summary, the conversation discusses finding the max length of a sub-string palindrome and a possible solution involving a for loop and while loop. The code provided has a bug in the if(L==R) block and the expert suggests that it is unreachable due to the while loop ending before it can be reached.
  • #1
member 428835
Hi PF!

I'm trying to find the max length of a sub-string palindrome. My logic is to have a left-most index called start that starts from string loc 0 and traverses to the end of the string via a for loop. Next I was thinking a while loop as long as L < R: I'd have a left index L=start and a right index R = string.length(). If ##L \neq R##, then ##R = R-1## and continue the while loop. However, if ##L = R## then ##L++## and ##R--##, we count this as a match, and continue. Only until L and R are the same (odd palindrome) or 1 away (even palindrome) do we replace the max palindrome length. However, I have a few bugs. Here's what I have, and any help is much appreciated.

C++:
#include <iostream>
#include <vector>
#include <string> // for string class
class Solution {
public:
    int longestPalindrome(std::string str) {
        int n = str.length();
        int maxLen = 1;
        int count = 0;
        for (int start = 0; start < n; start++) {
            int L = start;
            int R = n - 1;
           
            while (R > L) {
                if (str[R] != str[L]) {
                    R--;
                    continue;
                }
                count ++;
                if (L == R) {
                    maxLen = std::max(maxLen, 2*count+1);
                    count = 0;
                    break;
                }
                if (L == R - 1) {
                    maxLen = std::max(maxLen, 2*count);
                    count = 0;
                    break;
                }
                L++;
                R--;
            }
        }
        return maxLen;
    }
};
int main()
{
    std::string s_ = "yyureeeerl";
    Solution ob1;
    auto sol = ob1.longestPalindrome(s_);
    std::cout << sol << "\n";

    return 0;
}
 
Technology news on Phys.org
  • #2
I didn't spend that much time on your code, but the one obvious problem I can see is that the if(L==R) block is unreachable because the while loop is over when that happens!
 
  • Like
Likes member 428835

Related to Max length of substring-palindrome

What is a substring-palindrome?

A substring-palindrome is a string of characters that reads the same forward and backward, and is a part of a larger string of characters.

What is the maximum length of a substring-palindrome?

The maximum length of a substring-palindrome depends on the length of the larger string it is a part of. It can range from 1 (a single character) to the length of the entire string.

How is the maximum length of a substring-palindrome determined?

The maximum length of a substring-palindrome is determined by finding the longest sequence of characters that reads the same forward and backward within the larger string. This can be done through various algorithms and techniques.

Can a substring-palindrome be longer than half the length of the larger string?

Yes, a substring-palindrome can be longer than half the length of the larger string. It is possible for the longest substring-palindrome to have a length equal to or greater than half the length of the larger string.

What is the significance of finding the maximum length of a substring-palindrome?

Finding the maximum length of a substring-palindrome can be useful in a variety of applications, such as identifying patterns in DNA sequences, analyzing text for linguistic purposes, or solving mathematical problems. It can also help in improving algorithms and data structures for more efficient processing of strings.

Similar threads

  • Programming and Computer Science
Replies
10
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
22
Views
2K
  • Programming and Computer Science
2
Replies
55
Views
4K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
2
Replies
40
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
3
Replies
75
Views
4K
  • Programming and Computer Science
4
Replies
118
Views
7K
  • Computing and Technology
Replies
2
Views
65
Back
Top