这个回溯代码如何确保两个字符串没有共同的元素？

Question

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized. The two subsequences are disjoint if they do not both pick a character at the same index. Return the maximum possible product of the lengths of the two palindromic subsequences. For e.g., if s = "leetcodecom", the output should be 9 (two strings are ete and cdc, etc.).

借助一些在线帮助，我想出了以下代码：

class Solution {
public:
    int res;
    
    bool isPalindrome(string& s) {
        int i=0, j=s.size()-1;
        while(i<j && s[i]==s[j]) {
            i++;
            j--;
        }
        return i>=j;
    }
    
    void helper(string& s, string& s1, string& s2, int start) {
        if(start>=s.size()) {
            if(isPalindrome(s1) and isPalindrome(s2)) {
                res=max((int)res, (int)s1.size()*(int)s2.size());
            }
            return;
        }

        s1+=s[start];
        helper(s, s1, s2, start+1);
        s1.pop_back();
        
        s2+=s[start];
        helper(s, s1, s2, start+1);
        s2.pop_back();
        
        helper(s, s1, s2, start+1);
    }
    
    int maxProduct(string s) {
        res=0;
        string s1, s2;
        helper(s, s1, s2, 0);
        
        return res;
    }
};

这有效并获得 ACed，但我不确定它如何确保两个字符串 不相交 。我期待进行检查以确保这一点并更新 res 如果两个字符串不相交。

什么给了？

谢谢！

Answer 1

乍一看好像是DP（动态规划）

最初的问题听起来像这样。

Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized.

helper 解决了这个问题的更通用版本：

Given a string s, find two disjoint palindromic subsequences of s with the specified prefixes s1 and s2 such that the product of their lengths is maximized.

它使用递归来做到这一点。我们可以将所有可以想象的情况分为三类：

第一个字母是第一个子序列的一部分，在这种情况下，我们将这个字母附加到前缀 s1 并为字符串的其余部分解决相同的问题 s.
第一个字母是第二个子序列的一部分，在这种情况下，我们将这个字母附加到前缀 s2 并为字符串 s 的其余部分解决相同的问题。
第一个字母既不是第一个子序列的一部分，也不是第二个子序列的一部分，在这种情况下，我们可以忽略这个字母，只解决字符串其余部分的问题 s。

对helper的三个递归调用正好对应这三种情况。从这些案例的构造中，您可能会看到 none 个字母可能同时出现在两个序列中。

离问题越来越近了。在对 helper 的递归调用期间，初始字符串 s 的每个字符只能出现在 s1 （第一种情况）或 s2 （第二种情况）或被拒绝（第三种情况） .您可能会在代码中准确地看到这一点。字符被放入 s1 然后递归调用发生，然后它被弹出，然后它被放入 s2，然后递归调用发生，它被弹出，然后再次递归调用。

Answer 2

代码确保不相交，因为 helper 中的两个递归 steop 块永远不会将相同的字符拉入 s1 和 s2。

首先，每次调用 helper 都不会 return 直到处理字符串直到结束，包括触发的所有递归情况。然后 pop_back 将 return 各个序列恢复到其原始值，在此递归级别。

    s1+=s[start];
    helper(s, s1, s2, start+1);
    s1.pop_back();
    
    s2+=s[start];
    helper(s, s1, s2, start+1);
    s2.pop_back();

每当第一个块完成并且控制权落到第二个块时，s1 将返回到它在进入此递归级别时的值。之前放入 s1 的一些相同字符被添加到 s2。但它们从未同时出现在两者中。

    helper(s, s1, s2, start+1);

此行推进递归以搜索从所有位置开始的子序列。但是这里，s1 或 s2 没有添加任何字符。只有 start 索引向前移动。所以还是那句话，因为没有加字符，所以不能加普通字符。

在整个递归过程中，s1 和 s2 包含 s 的潜在交错子序列，但 s 中的字符从未出现在 s1 和 s2 同时.

这很难理解，因为它不是函数递归，因为序列通过引用传递并被破坏性地操纵。这是一种迭代过程，使用递归为其提供回溯堆栈；一个下推式自动机，笼统地说。它甚至没有 return 一个值；它的输出是对递归范围之外的成员变量的副作用。

你必须凭直觉知道 s2+=s[start]; 和 s2.pop_back() 是平衡的、成对的类似堆栈的操作，它们使序列进入相同的状态，而不管下面的递归中发生了什么（因为下面的递归执行了相同的平衡 push/pop 对）。此外，下面的递归总是在 start + 1 处，并且只向右移动，所以它永远不会向任何一个子序列添加相同的字符。所以我们可以看到在同一个帧中存在局部互斥，加上对下层递归帧的互斥。

这个回溯代码如何确保两个字符串没有共同的元素？

How does this backtracking code ensure that the two strings don't have common elements?

c++

algorithm

backtracking

disjoint-sets