Cue programming challenge

[Jazpy]

This things has been kicking my ass all day: http://challenge.cueup.com/

"The password is the longest substring that is the same in reverse.

As an example, if the input was "I like racecars that go fast"
the password would be "racecar"."

Below is the solution that I came up with, sadly it doesn't work:

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string main, bwd = "", test = "", pass = "";

    cin >> main;

    for (int j = 0; j < main.length(); j++){
        bwd += main.at(main.length() - 1 - j);
    }
    
    for (int i = 0; i < main.length(); i++){
        test = main.at(i);

        size_t found = bwd.find(test);

        if (found != string::npos){

            string pass_temp = "";
            int counter = 1;

            while (bwd.find(test) != string::npos){
                pass_temp = test;
                test += main.at(i + counter);

                counter++;
            }

            if (pass_temp.length() > pass.length()){
                pass = pass_temp;
            }

        }
    }

    cout << pass << endl;

    return 0;
}

The program is crashing with an std:: out_of_range, which I think is happening within the while loop, could anyone give me a nudge in the right direction?

[Smac89]

This is a longest palindrome substring problem.

http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

[Volatile Pulse]

You have a lot of issues here. I'll display a comment with each line and what it is doing, then point out specific issues that are not doing as you expect.

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string main, bwd = "", test = "", pass = "";

    // Allows the user to enter a string
    // This only stores the characters up until the first whitespace
    // encountered. If you type "I like to drive..." main will contain
    // "I". Do some research on cin.getline()
    // http://www.cplusplus.com/reference/istream/istream/getline/
    cin >> main;

    // Runs a loop for the number of characters in main and
    // assigns bwd with the reverse of main
    // Once the above is fixed, bwd will be "...evird ot ekil I"
    // Is this what you really want?
    for (int j = 0; j < main.length(); j++){
        bwd += main.at(main.length() - 1 - j);
    }

    // Runs a loop for the number of characters in main
    for (int i = 0; i < main.length(); i++){
        // test is set to the specific character at i
        test = main.at(i);

        // this finds the first instance of test, which is
        // only one character.
        // This will work if you figure out how to change
        // test to be set to an entire word
        size_t found = bwd.find(test);

        // As long as you found a palindrome (currently just
        // one character long...which happens a lot)
        if (found != string::npos){

            // pass_temp is set to empty
            string pass_temp = "";
            // not sure why this is a while loop when you
            // could have just used a for loop
            // for (int counter = 0; bwd.find(test) != string::npos; counter ++)
            int counter = 1;

            // This will be true as long as test is a palindrome
            // has the same effect as the above if conditional
            while (bwd.find(test) != string::npos){
                // pass_temp is assigned the palindrome
                pass_temp = test;

                // I believe this is your attempt to turn test into a word
                // the problem is, the code doesn't know the difference
                // between a space and a letter and a period.
                
                // This is also where you're getting your out of range error
                // i + counter is going to be >= length
                // include that in the conditional of the while or for
                test += main.at(i + counter);

                counter++;
            }
            
            // Set the new password if temp is longer
            if (pass_temp.length() > pass.length()){
                pass = pass_temp;
            }

        }
    }

    cout << pass << endl;

    return 0;
}

I was a little confused reading down your code since I was expecting something differently, but just read through it all and you should be able to figure it out.

@Smac89
A lot of people prefer to solve the problems themselves before learning the optimal way of doing the same thing. Also, someone doesn't always learn by just giving them the answer.

[Jazpy]

Thanks to both for the help, I modified it so it separates the main string into words, and then searches those words in the backwards string, it works as long as the words are separated only by spaces, the only problem is that the challenge gives me a really long string with no spaces to separate words, so I don't think this solution should work.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

vector<string> &split(const string &s, char delim, vector<string> &elems) {
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
        elems.push_back(item);
    }
    return elems;
}

vector<string> split(const string &s, char delim) {
    vector<string> elems;
    split(s, delim, elems);
    return elems;
}

int main(){
    string main, bwd = "", test = "", pass = "";

    getline(cin, main);

    for(int j = 0; j < main.length(); j++){
        bwd += main.at(main.length() - 1 - j);
    }

    vector<string> words = split(main, ' ');

    for(int i = 0; i < words.size(); i++){

        size_t found = bwd.find(words[i]);

        if (found != string::npos){
            string pass_temp = "";
            pass_temp = words[i];

            if (pass_temp.length() > pass.length())
                pass = pass_temp;
        }

    }

    cout << pass << endl;

    return 0;
}

Is this something I could modify so it works with the long, spaceless string? Or am I better off starting from scratch?

[manudude03]

The most intuitive solution for me is to use 3 for loops. It is a bit of a brute force method, but works. The first is for the starting point, the second is for the end point, and the third is to test if the substring is a palindrome. If you find that you have a palindrome, then check if the length is larger than the longest palindrome found, and if so, print it out.

edit: This solution is only for strings without spaces I believe, you may need a little code at the start to strip away the spaces.

[Volatile Pulse]

If racecar was the password for your given example, its any valid substring, it doesn't have to be a complete word. That's the part I missed initially. I believe you were actually closer with your first program if thats the case. Another thing you may need to consider is, if the input starts as "Racecars are fast..." Is the password going to be racecar or aceca. The only real changes you needed to make was reading of main using getline, and fixing your out of bounds issue. I also suggest maybe making that inner while loop a for statement as well.

I'm at work right now, but if you can't figure it out by the time I get home, I'll give you the pointers I suggested in coding format. Good luck.

[Josue Molina]

This is the result of sitting down and calmly solving this problem first with pencil and paper; the program codes itself:

#include <iostream>

using namespace std;

bool IsPalindrome(string s)
{
    for (int i = 0; i < s.length() / 2; i++)
        if (s[i] != s[s.length() - i - 1])
            return false;
    return true;
}

int main()
{
    string s = "I like racecars that go fast";

    for (int i = s.length(); i >= 2; i--)
        for (int j = 0; j <= s.length() - i; j++)
            if (IsPalindrome(s.substr(j, i)))
                cout << s.substr(j, i) << endl;

    return 0;
}

[Smac89]

Nice ^

Now make it solve the problem in O(N^2) time

[Josue Molina]

That's beyond the scope of this question, but it is a good exercise. :-P

[Catfish4]

We could try to construct the palindromes instead of searching for them?

Case 1: try to construct palindromes of odd length:
- select a character
- check if left and right match
- check if outer left and right match
- ... and so on, until they don't
- save the palindrome if it's longer than the previous one we err... found

Case 2: palindromes of even length:
- select two neighboring characters which match
- continue as in Case 1

Complexity should be O(2*n²) which is the same as O(n²)?

[Smac89]

Or each letter in the string could act like a linked list.

start at index 1 and progress through the string
set a temp linked list at the index 0
If node at index k is equal to node at index k-1
If the (node at index k-1).prevNode != NULL
Node[k-1] = Node[k-1].prevNode
Else Store indexes of longest palindrome string found and temp linked list will now be pointing to current letter the iteration is at

This could possibly be O(N) solution

[Josue Molina]

Catfish4:
Complexity should be O(2*n²) which is the same as O(n²)?

That's correct. I implemented your algorithm and it's noticeably faster than mine.

Edit: here is the program, if interested.

#include <iostream>
#include <list>

std::string LargestPalindromeSubstring(std::string s)
{
    std::list<char> lp;

    // Odd Palindromes
    for (int i = 0; i < (int)s.length(); i++)
    {
        int c = 1;
        std::list<char> p;
        p.push_front(s[i]);

        while (i - c >= 0 && i + c < (int)s.length() && s[i - c] == s[i + c])
        {
            p.push_front(s[i - c]);
            p.push_back(s[i + c++]);
        }

        if (p.size() > lp.size())
        {
            lp = p;
        }
    }

    // Even Palindromes
    for (int i = 0; i < (int)s.length() - 1; i++)
    {
        if (s[i] != s[i + 1])
        {
            continue;
        }

        int c = 1;
        std::list<char> p;
        p.push_front(s[i]);
        p.push_back(s[i + 1]);

        while (i - c >= 0 && i + 1 + c < (int)s.length() && s[i - c] == s[i + 1 + c])
        {
            p.push_front(s[i - c]);
            p.push_back(s[i + 1 + c++]);
        }

        if (p.size() > lp.size())
        {
            lp = p;
        }
    }

    std::string r = "";

    for (std::list<char>::iterator it = lp.begin(); it != lp.end(); it++)
    {
        r += *it;
    }

    return r;
}

int main()
{
    std::cout << LargestPalindromeSubstring("I like racecars that are fast.");

    return 0;
}

@Smac89, I don't see how that finds the largest palindrome sub-string, let alone how it runs in O(n) time.

[Smac89]

Here it is (Python):

#!/usr/bin python
class node:
	def __init__(self, char):
		self.char = char
		self.prev = None
		self.index = 0
		
	def __eq__(self, other):
		if other != None:
			return self.char == other.char
		return 0
		
	def __repr__(self):
		return self.char

def findLongestPaliSubstrs(l_string):
	p_str = map(node, l_string)
	seq = p_str[0]
	p_seq = []
	even = 1
	for k in xrange(1, len(l_string)):
		p_str[k].prev = p_str[k-1]
		p_str[k].index = k
		if even:
			if seq and p_str[k] == seq:
				seq = seq.prev
				continue
			p_seq.append({k-1-seq.index: [seq.index, k-1]})
			seq = p_str[k]
			even = 0
		elif seq and p_str[k] == seq.prev:
			even = 0
			seq = seq.prev
		else:
			p_seq.append({k-1-seq.index: [seq.index, k-1]})
			even = 1
			seq = p_str[k]
	return p_seq

mystring = raw_input()
l = sorted(findLongestPaliSubstrs(mystring), reverse=True)
print mystring[204:211] #This is the longest string index it found for the problem 

it finds all palindrome substrings but can be easily tweaked to find just the longest

I was wrong :(. It does not show the correct results for some strings. But the answer it found for the problem is right

[Jazpy]

Wow, I wasn't expecting so many replies, thanks everyone for helping, I think my problem was that I didn't really have a solid understanding of strings.

[Josue Molina]

Sorry; we hijacked your thread by turning it into an algorithm analysis feast.

[cire]

I took a slightly different approach. I built a map of character ranges which indicate possible palindromes, keyed on the length of the possible palindrome (in descending order.) These ranges were generated by finding pairs of the same letter in the string, since every palindrome must begin and end with the same letter. Sequences of 2 letters are discarded as uninteresting. Sequences of more than 2 are filtered; if the 2nd and 2nd to last character in the sequence aren't equal the sequence is discarded, otherwise it is added to the map to be processed as a possible palindrome later.

When that's done, I simply iterated through the map, checking the ranges to see if they were palindromes as I went. Given the order, the first palindrome I found would be the longest.

It's probably a little more complicated than it need be.

#include <iostream>
#include <algorithm>
#include <functional>
#include <cctype>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <vector>

bool isPalindrome(const char* beg, const char* end)
{
    while (std::tolower(*beg) == std::tolower(*end) && ++beg < --end)
        ;

    return !(beg < end);
}

std::string findLongestPalindrome(const char* s)
{
    const char* end = s + std::strlen(s);

    std::map <unsigned, std::vector<std::pair<const char*, const char*>>, std::greater<unsigned>> candidates;

    {
        std::set<char> processed;
        const char* cursor = s;

        std::vector<const char*> locations;
        locations.reserve(1000);

        while (*cursor != '\0')
        {
            if (!processed.count(std::tolower(*cursor)))
            {
                processed.insert(std::tolower(*cursor));

                locations.clear();
                locations.push_back(cursor);

                const char* next = cursor ;
                while ((next = std::find_if(next+1, end, [=](char ch) { return std::tolower(ch) == std::tolower(*cursor); })) != end)
                    locations.push_back(next);

                if (locations.size() > 1)
                    for (unsigned i = 0; i < locations.size() - 1; ++i)
                        for (unsigned j = i+1; j < locations.size(); ++j)
                        {
                            unsigned candidateLength = locations[j] - locations[i] + 1;

                            if ( (candidateLength > 2 && *(locations[j]-1) == *(locations[i]+1)) ) 
                                candidates[locations[j] - locations[i] + 1].push_back(std::make_pair(locations[i], locations[j]));
                        }
            }

            ++cursor;
        }
    }

    for (auto & candidateList : candidates)
        for (auto & candidate : candidateList.second)
            if (isPalindrome(candidate.first, candidate.second))
                return std::string(candidate.first, candidate.second + 1);

    return std::string();
}

[Josue Molina]

@Jazpy, at the end of the challenge, they'll ask you to send them your resume. :-)