Given a string S of length N, return a string that is the result of replacing each '?' in the string S with an 'a' or a 'b' character and does not contain three identical consecutive letters (in other words, neither 'aaa' not 'bbb' may occur in the processed string).
Examples:
Given S="a?bb", output= "aabb"
Given S="??abb", output= "ababb" or "bbabb" or "baabb"
Given S="a?b?aa", output= "aabbaa"
1<=n<= 500000
I solved the problem using backtracking, but my solution is slow and won't work for greater N values, is there a better approach?
My solution:
#include <bits/stdc .h>
using namespace std;
bool isValid(string &s, int pos)
{
if (pos < 2)
return true;
for (int i = 1; i < pos; i )
{
if (s[i - 1] == s[i] && s[i] == s[i 1])
{
return false;
}
}
return true;
}
void solve(string &s, int pos, string &ans)
{
if (pos == s.length())
{
ans = s;
return;
}
if (!isValid(s, pos))
return;
if (s[pos] == '?')
{
s[pos] = 'a';
if (isValid(s, pos))
solve(s, pos 1, ans);
s[pos] = 'b';
if (isValid(s, pos))
{
solve(s, pos 1, ans);
}
s[pos] = '?';
}
else
solve(s, pos 1, ans);
}
int main()
{
string s;
cin >> s;
string ans;
solve(s, 0, ans);
cout << ans;
return 0;
}
CodePudding user response：
first of all x??y with more than 1? would always pass
a??b => abab(produce no increase of length on both side, *no impact* at following)a??a => abba(no impact)a???????????????????b => ab?????????????????ab
so you only need to consider the case with single ?
aa? => aab(no other possibility)a?a => aba(no impact)
so the only problem comes to a?b
aa?b => aabb(as describe inaa?)ba?b => baab(no impact)^a?b=>^aab(only for start, no impact)
You did at most 2 look-back and 2 look-ahead so this is a O(n) solution,
If it can contain invalid input, simply run another O(n) check
CodePudding user response：
The O(n) dynamic program has four states: a character is either a_first, a_second, b_first or b_second. Let dp[i] represent the possibility of creating a valid string up to index i. Then:
dp[i][a_first] = True
dp[i][a_second] = True
dp[i][b_first] = True
dp[i][b_second] = True
where i < 0
if s[i] == '?':
dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
dp[i][a_second] = dp[i-1][a_first]
dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
dp[i][b_second] = dp[i-1][b_first]
else if s[i] == 'a':
dp[i][a_first] = dp[i-1][b_first] or dp[i-1][b_second]
dp[i][a_second] = dp[i-1][a_first]
dp[i][b_first] = False
dp[i][b_second] = False
else:
dp[i][a_first] = False
dp[i][a_second] = False
dp[i][b_first] = dp[i-1][a_first] or dp[i-1][a_second]
dp[i][b_second] = dp[i-1][b_first]
where i ≥ 0
To get the strings, we can follow the paths backwards that maintain True throughout and keep the consecutive character constraint.
Python code:
def f(s):
dp = [[None] * 4 for _ in range(len(s))]
def get_dp(i, j):
return True if i < 0 else dp[i][j]
for i in range(len(s)):
if s[i] == '?':
dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
dp[i][1] = get_dp(i-1, 0)
dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
dp[i][3] = get_dp(i-1, 2)
elif s[i] == 'a':
dp[i][0] = get_dp(i-1, 2) or get_dp(i-1, 3)
dp[i][1] = get_dp(i-1, 0)
dp[i][2] = False
dp[i][3] = False
else:
dp[i][0] = False
dp[i][1] = False
dp[i][2] = get_dp(i-1, 0) or get_dp(i-1, 1)
dp[i][3] = get_dp(i-1, 2)
# Build the output
result = []
i = len(s) - 1
need = None
while i >= 0:
if dp[i][0] and need != 'b':
result.append('a')
need = None if (len(result) == 1 or result[-2] == 'b') else 'b'
i-= 1
elif dp[i][1] and need != 'b':
result.extend(['a', 'a'])
need = 'b'
i -= 2
elif dp[i][2] and need != 'a':
result.append('b')
need = None if (len(result) == 1 or result[-2] == 'a') else 'a'
i -= 1
elif dp[i][3] and need != 'a':
result.extend(['b', 'b'])
need = 'a'
i -= 2
else:
return ""
return "".join(reversed(result))
Output:
strs = [
"a?bb", # "aabb"
"??abb", # "ababb" or "bbabb" or "baabb"
"a?b?aa", # "aabbaa"
"?bb?",
"aa?bb", # NO SOLUTION
"aa??aa", # "aabbaa"
"ab???bb?",
"????",
"??",
"?????",
"??????"
]
for s in strs:
print("%s\n%s\n" % (s, f(s)))
"""
a?bb
aabb
??abb
baabb
a?b?aa
aabbaa
?bb?
abba
aa?bb
aa??aa
aabbaa
ab???bb?
abbaabba
????
abaa
??
aa
?????
aabaa
??????
baabaa
"""
CodePudding user response：
An iterative backtracking solution.
isValidonly checks whether inserting a charcat positionposwould create an issue, without iterating over the whole string;maintain a variable
int dir = -1to know whether we're moving forward or backwards in the string (this is only important so that we know in which direction to move when skipping over a non-?character in the original string);forest of
if/else if/elseto decide where we're at (non-?to skip, or fresh?going forward, or already trieda, or already tried bothaandb);solvehas a boolean return value which istrueif a solution was found (pos == s.length()), orfalseif no solution was found (pos == (unsigned int) -1).
#include <iostream>
#include <vector>
bool isValid(char c, std::string const &s, unsigned int pos)
{
return ((pos < 2 || s[pos - 2] != c || s[pos - 1] != c)
&& (pos < 1 || pos 1 >= s.length() || s[pos - 1] != c || s[pos 1] != c)
&& (pos 2 >= s.length() || s[pos 1] != c || s[pos 2] != c));
}
bool solve(std::string const &in, std::string &out)
{
unsigned int pos = 0;
int dir = 1;
out = in;
while (pos < in.size())
{
if (in[pos] != '?') // nothing to do: keep moving (forward or backward)
{
pos = dir;
}
else if (out[pos] == '?') // going forward, will try 'a' then 'b'
{
dir = 1;
if (isValid('a', out, pos))
{
out[pos] = 'a';
pos = dir;
}
else if (isValid('b', out, pos))
{
out[pos] = 'b';
pos = dir;
}
else
{
dir = -1;
pos = dir;
}
}
else if (out[pos] == 'a' && isValid('b', out, pos)) // going backward, already tried 'a'
{
out[pos] = 'b';
dir = 1;
pos = dir;
}
else // already tried everything: backtrack
{
dir = -1;
out[pos] = '?';
pos = dir;
}
}
return (pos == in.size());
}
int main(void)
{
std::vector<std::string> ins = {"a?bb", "??abb", "a?b?aa", "aa?bb"};
std::vector<std::string> outs = {"", "", "", "", ""};
for (unsigned int i = 0; i < ins.size(); i)
{
if (solve(ins[i], outs[i]))
std::cout << ins[i] << " --> " << outs[i] << std::endl;
else
std::cout << ins[i] << " --> NO SOLUTION" << std::endl;
}
return 0;
}
Output:
a?bb --> aabb
??abb --> ababb
a?b?aa --> aabbaa
aa?bb --> NO SOLUTION
CodePudding user response：
You can try the algorithm below. Let's start changing sequences of ? into a or b from left to right.
For a single ?
a?a -> aba
a?b -> try aab, then (in case of aa?b) try abb
b?a -> try bba, then (in case of bb?a) try baa
b?b -> bab
For a long (more then one ?) sequence start adding alternating a and b from both ends:
a?????????b -> ab???????ab -> aba?????bab -> abab???abab -> ababa?babab -> ababaababab
We can have 4 possible pattern all being valid
a?????????a -> ababa .... ababa, so we'll have either abababa or ababbaba
a?????????b -> ababa .... babab, so we'll have either abababab or ababbabab
b?????????a -> babab .... ababa, so we'll have either babababa or babaababa
b?????????b -> babab .... babab, so we'll have either bababab or babaabab
CodePudding user response：
I quickly tried out the solution I proposed in the comments:
#include <iostream>
#include <string>
int main(void)
{
std::string s = "?????aaa??bbaa????";
std::cout << s <<'\n';
for(char &c:s)
if(c=='?')
c='a';
std::cout << s <<'\n';
for(int i =0; i<s.size()-2; i )
{
if(s[i] == 'a'
&& s[i 1] == 'a'
&& s[i 2] == 'a' )
{
s[i 1] = 'b';
i ;
}
}
std::cout << s <<'\n';
return 0;
}
It seems to be conformant with the given rules. but maybe there's some case to check and fix.