Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром

#include <iostream>
using namespace std;
int main()
{
    string str;
    cin>>str;
    string newstr;
    int j = str.length()-1;
    bool visited[100];
    for(int i = 0; i < 100; i++) visited[i] = false;
    for(int i = 0; i<j && i < str.length()/2+1; i++)
    {
        if (str[i] == str[j]) newstr.push_back(str[i]); else
        for(int g = i; g < j && g < str.length()/2+1; g++)
        {
            if (str[g] == str[j] && visited[g] == false) {newstr.push_back(str[g]); visited[g] == true; i = g; break;}
        }
    /*  for(int g = j; g > i && g >= str.length()/2+1; g--)
        {
            if (str[g] == str[i] && visited[i] == false) {newstr.push_back(str[g]); visited[i] == true; j = g; break;}
        }*/
        j--;
    }
    cout<<newstr;
    if (str.length()%2 == 0) cout<<str[str.length()/2]; else cout<<str[str.length()/2+1];
    for(int i = newstr.length()-1; i >=0; i--)
    cout<<newstr[i];
}

#include <iostream>
#include <algorithm>
#include <array>
#include <string>
 
std::string palindrome(const std::string& s) {
    if (s.size() == 0 || s.size() == 1) {
        return s;
    }
    if (s.front() == s.back()) {
        return s.front() + palindrome(s.substr(1, s.size() - 2)) + s.back();
    }
    std::array<std::string, 3> branches; 
    branches[0] = palindrome(s.substr(1));
    branches[1] = palindrome(s.substr(0, s.size() - 1));
    branches[2] = palindrome(s.substr(1, s.size() - 2));
 
    return *std::max_element(branches.begin(), branches.end(), []
        (const std::string& a, const std::string& b) {
            return a.size() < b.size();
        });
}
 
int main()
{
    std::string target{ "12343271" };
    std::cout << palindrome(target) << std::endl;
}

#include <iostream>
#include <cassert>
#include <algorithm>
#include <array>
#include <string>
#include <unordered_map>
#include <chrono>
 
// S('t' "alpha" 'h')
std::string palindrome(const std::string& s) {
    // so slow ... trying to search in cache
    static std::unordered_map<std::string, std::string> cache;
    if (cache.find(s) != end(cache)) {
        return cache[s];
    }
    //////////////////////////////////////////
    if (s.size() == 0 || s.size() == 1) {
        return s;
    }
    std::string alpha{ s.substr(1, s.size() - 2) };
    if (s.front() == s.back()) {
        std::string result = s.front() + palindrome(alpha) + s.back();
        cache[s] = result;
        return result;
    }
    std::array<std::string, 3> branches;
    // S(alpha t)
    std::string alpha_t{ s.substr(1) };
    branches[0] = palindrome(alpha_t);
    if (branches[0].size() == alpha_t.size()) {
        cache[s] = branches[0];
        return branches[0];
    }
    // S(h alpha)
    std::string h_alpha{ s.substr(0, s.size() - 1) };
    branches[1] = palindrome(h_alpha);
    if (branches[1].size() == h_alpha.size()) {
        cache[s] = branches[1];
        return branches[1];
    }
    // S(alpha)
    branches[2] = palindrome(alpha);
 
    auto result = std::max_element(branches.begin(), branches.end(), []
    (const std::string& a, const std::string& b) {
        return a.size() < b.size();
    }); 
    
    cache[s] = *result;
    return *result;
}

///////////////////////////////////////////////////////////////////////////////
//3.
///////////////////////////////////////////////////////////////////////////////
//Из данной строки удалите наименьшее количество символов
//так, чтобы получился палиндром.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <utility>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                                 T_str;
typedef T_str::size_type                            T_pos;
typedef T_pos                                       T_len;
typedef std::pair   < T_pos,            T_len   >   T_pos_and_len;
typedef std::map    < T_pos_and_len,    T_str   >   T_palindrom_of_pos_and_len;
///////////////////////////////////////////////////////////////////////////////
bool    ends_equal
    (
        T_str           const   &   s,
        T_pos_and_len   const   &   pos_and_len
    )
{
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    return      s[ pos              ]
            ==  s[ pos + len - 1    ];
}
///////////////////////////////////////////////////////////////////////////////
T_str   get_palindrom_of_pos_and_len
    (
        T_str                       const   &   s,
        T_palindrom_of_pos_and_len          &   palindrom_of_pos_and_len,
        T_pos_and_len               const   &   pos_and_len
    )
{
    auto    it  =   palindrom_of_pos_and_len.find( pos_and_len );
 
    if  (
            it  !=  palindrom_of_pos_and_len.end()
        )
    {
        return  it->second;
    }
 
    T_str   res;
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    if  (
                len
            <=  1
        )
    {
        res     =   s.substr( pos, len );
    }
    else if (
                ends_equal( s, pos_and_len )
            )
    {
        res     =       s[ pos ]
 
                    +   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   2
                                }
                            )
 
                    +   s[ pos ];
    }
    else
    {
        auto    L   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos,
                                    len     -   1
                                }
                            );
 
        auto    R   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   1
                                }
                            );
 
        res     =       L.size()
                    >   R.size()
                        ?   L
                        :   R;
    }//else
 
    palindrom_of_pos_and_len[ pos_and_len ]   =   res;
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
T_str   max_palindrom( T_str    const   &   s )
{
    T_palindrom_of_pos_and_len  palindrom_of_pos_and_len;
 
    return  get_palindrom_of_pos_and_len
                (
                    s,
                    palindrom_of_pos_and_len,
 
                    {
                        0,
                        s.size()
                    }
                );
}
///////////////////////////////////////////////////////////////////////////////
T_str   rand_str_with_size( int  size )
{
    const   T_str   LETTERS     =   "abcdefghijklmnopqrstuvwxyz";
    T_str           res;
 
    for( int  i{}; i < size; ++i )
    {
        res     +=  LETTERS[ rand() % LETTERS.size() ];
    }
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        T_str   s   =   rand_str_with_size(2000);
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  s
                    <<  std::endl
                    <<  std::endl
                    <<  "-> ";
 
        T_str   res     =   max_palindrom(s);
 
        std::cout   <<  res
                    <<  std::endl;
 
        system("pause");
    }//for
}