C/C++ Max length of substring-palindrome

  • Thread starter Thread starter member 428835
  • Start date Start date
  • Tags Tags
    Length Max
AI Thread Summary
The discussion focuses on finding the maximum length of a substring palindrome using a specific algorithm. The proposed logic involves using a for loop to iterate through the string with a left index (L) and a right index (R). The while loop is designed to compare characters from both ends, adjusting the indices based on matches and counting potential palindrome lengths. However, a critical bug is identified: the condition where L equals R is unreachable because the while loop terminates when L is no longer less than R. This oversight prevents the algorithm from correctly identifying odd-length palindromes. The code provided demonstrates the implementation but requires adjustments to address this issue for accurate palindrome length calculation.
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
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
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
hi; i purchased 3 of these, AZDelivery 3 x AZ-MEGA2560-Board Bundle with Prototype Shield and each is reporting the error message below. I have triple checked every aspect of the set up and all seems in order, cable devices port, board reburn bootloader et al . I have substituted an arduino uno and it works fine; could you help please Thanks Martyn 'avrdude: ser_open(): can't set com-state for "\\.\COM3"avrdude: ser_drain(): read error: The handle is invalid.avrdude: ser_send(): write...

Similar threads

Replies
1
Views
1K
Replies
22
Views
3K
Replies
8
Views
2K
Replies
40
Views
3K
Replies
11
Views
4K
Back
Top