通过重新排列字母使回文字符串成为非回文字符串

Question

问:通过重新排列字母，使回文字符串成为非回文字符串。

当我提交代码时，我只想知道为什么我的解决方案在一些测试用例中失败(错误答案)。我相信有一个简单的解决方案，比如对整个字符串进行排序？

void makeNonPalindrome(string& s)
{
    bool ans = false;
    int l = s.length();
    if(l % 2 == 0)
    {
        for(int i = l/2; i < l; i++)
        {
            if(s[l/2 - 1] != s[i])
            {
                swap(&s[l/2 - 1],&s[i]);
                ans = true;
                break;
            }

        }
        if(!ans)
        {
            for(int i = 0; i < l/2-1; i++)
            {
                if(s[l/2 - 1] != s[i])
                {
                    ans = true;
                    break;
                }
            }
        }
    }
    else
    {
        for(int i = l/2 + 1; i < l; i++)
        {
            if(s[l/2 - 1] != s[i])
            {
                swap(&s[l/2 - 1],&s[i]);
                ans = true;
                break;
            }

        }
        if(!ans)
        {
            for(int i = 0; i < l/2-1; i++)
            {
                if(s[l/2 - 1] != s[i])
                {
                    ans = true;
                    break;
                }
            }
        }
        if(!ans)
        {
            if(s[l/2] != s[0])
            {
                swap(&s[l/2],&s[0]);
                ans = true;
            }
        }
    }
    if(ans)
        cout << s << '\n';
    else
        cout << -1 << '\n';
}

Answer 1

重新排列回文，使其成为非回文，可以非常快地完成，只需尝试交换字符串中的两个相邻字母(如果它们不同)。

例如，在'bob'中，您需要找到第一个不同的相邻字母(在我们的示例中是b和o )，并交换它们。那么结果将是'obb'，它不是一个回文。

void makeNonPalindrome(std::string& s) {
    char tmp;
    for (unsigned i = 0; i < s.length() - 1; i++) {
        if (s[i] != s[i+1]) {  // then swap s[i] and s[i+1]
            tmp = s[i];
            s[i] = s[i+1];
            s[i+1] = tmp;
            std::cout << s << '\n';
            return;
        }
    }
    std::cout << -1 << '\n';
}

这是一个使回文非回文的更简单的方法。注意:这个函数假设输入确实是一个回文，所以如果你给它一个像'oob'这样的字符串，它将输出一个回文的'bob'。