Search code examples
c++palindrome

Substring of string in C++ do not coincide with index

When i try to solve problem Longest Palindromic Substring from leetcode, something weird happened, i could not understand what's wrong with it. Here are the source code i wrote, and also the weird output.

#include <iostream>
#include <string>

class Solution {

public:

    std::string longestPalindrome(std::string s) {

        // incase s is empty
        if (s.size() <  1) return "";

        int start = 0, end = 0;
        for (std::string::size_type i = 0; i < s.size(); i++) {

            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);
            int len  = std::max(len1, len2);

            if (len > (end - start + 1)) {
                start = i - (len-1)/2;
                end   = i + (len)  /2;
            }    
        }

        std::cout << std::endl;
        std::cout << "start: " << start << ", end: " << end << std::endl;
        return s.substr(start, end+1);

    }

private:

    int expandAroundCenter(std::string s, int left, int right)
    {    
        while (left >= 0 && right < s.size() && s[left] == s[right]) 
        {
            left--;
            right++;
        }

        return right-left-1;            
    }        
};

int main(void)
{
    std::string s1 = "ababd";
    std::string s2 = "addbbcc";
    std::string s3 = "bb";
    Solution sol;
    std::cout << sol.longestPalindrome(s1) << std::endl;
    std::cout << sol.longestPalindrome(s2) << std::endl;
    std::cout << sol.longestPalindrome(s3) << std::endl;
    std::cout << std::endl;
    return 0;    
}

And the output is following

output

This is weird why the length of the substring do not coincide with the range from indexes.

Solution

  • I would suggest running your code in your debugger and setting watches on start and end. Chances are, this isn't working the way you think it is supposed to.

    Recall the definition of string::substr()

    string substr (size_t pos = 0, size_t len = npos) const;

'pos' = start position of the substring
'len' = Number of characters to include in the substring

    It seems to me that you might be thinking that string::substr() works by giving a start and end position, which is not the case.

    I hope this helps. If i am incorrect in my assumption about string::substr(), do the following:

    1. Setup the debugger like I suggested.
    2. Try more sophisticated tests to gain more insight into the problem.

    Note: In the future, try to document your code better especially if you are going to be posting on an online forum for help/solutions.