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...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...

Similar threads

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