Can someone help me solve this Coding problem?
Posted by Plane_Pen_1520@reddit | learnprogramming | View on Reddit | 23 comments
We are given 2 strings Src and Target. We have to convert Src to target by performing operations. an operation involves removing a suffix from the current string and add it to the beginning (For eg. "abcd" -> "cdab" or "dabc" or "bcda").
We have to tell how many different ways of converting Src to Target using exactly K operations. A way is different if there is at-least one time where the sequence of operations was different.
codetree_bnb@reddit
Hello, could you provide more details about the constraints? Knowing the constraints for k would help me assist you better.
Plane_Pen_1520@reddit (OP)
Size of Src and Target was between 1 and 1000. And
1<k<=10\^6
codetree_bnb@reddit
My solution is a bit tricky to explain in words, so I wrote some code to solve the problem. Unfortunately, I can't include it in my comment. Would you like me to explain the solution in words?
mrbaggins@reddit
This is a math problem, not a coding one (though you can code a brute force solution)
A string of
ncharacters where the only operation allowed is to wrap it around hasnpossible arrangements.Each operation can move between
1andxletters aroundGiven you're tasked with finding
koperation counts, looping repeatedly is probably allowed. IE:abcd -> dabc in 5 changes requires looping.
First, work out how far it's wrapped around,
dby locatingsrc[0]character in target string and getting it's index.So, the question really becomes, "how many different ways can you add
knumbers in the range1tonto equald"CodeTinkerer@reddit
This assumes the letters are unique (that may be too strong an assumption).
For example, suppose
srcanddstwereaaaaand k was 4. Assuming we're talking about a proper suffix (a string can't be a suffix of itself, nor can it be the empty string), then any suffix picked would work for an operation. As there are 3 suffixes, you have 3^4 choices (each of 3 possible suffixes for each of 4 operations). Ifkis 0, then there's only 1 way to do it which is to do nothing.If all the letters are unique, then your analysis makes sense.
mrbaggins@reddit
Fair, so you now need to loop the entire string (or enough of it) to confirm the new starting point.
ckje@reddit
This is exactly what I was thinking. The problem because much more annoying when the string has duplicated characters.
CodeTinkerer@reddit
You could generate all possible shifted strings, put them in a set. If the size of the set is smaller than the number of rotated strings, then there's a duplicate string.
By rotates strings, I mean, for a 6 letter word, rotate suffix of len 1, rotate suffix of len 2, etc. up to rotate suffix of length 5.
There are other ways to detect duplicates, but, as you say, it makes it pretty annoying.
qrrbrbirlbel@reddit
Their solution could still work if instead of finding one arrangement represented by index
d, we find up tonarrangements each represented by an index. We could put all valid indices in a set.E.g., if we have
src == “baba”,target == “abab”, then instead ofd == 1, we would haveset == {1, 3}.Now we check all
n**ksums to see how many exist in the set. This would all be super slow though given the constraints OP gave in another comment.Plane_Pen_1520@reddit (OP)
Can you give me an example with a small test case, if that's possible?
mrbaggins@reddit
In
k=3operations: abcdefg -> efgabcd.ahas moved from 0 to 3 sod=4The question is now "How many additions of 3 terms under 7 are there that result in x mod 7 = 4"
DeepMisandrist@reddit
Target has to be a rotation of Src. Here, any of the n rotations of Src can match Target. e.g., if Src = 'aaa' and Target = 'aaa', then all the 3 rotations of Src match Target. If Src = 'abc' and Target = 'bca', only 1 rotation matches.
We'll always have a rotation of Src after each operation. In 1 operation(rotation), we can transform into any of the N rotations of Src, because we can choose any length suffix and bring it to front. So no matter what we do in the first K - 1 operations, we can choose our Kth operation s.t. the final string becomes Target, given that it's also a rotation.
For the first K - 1 operations, we have N choices at each step - this gives us N \^ (K - 1) choices.
Let's say M rotations of Src match Target, then that gives us M choices for the Kth operation.
So, total number of ways we can choose our operations is N\^(K - 1) * M.
A complication arises if we're not allowed to do no-op rotations. (we can rotate ABC into itself by choosing a suffix length of 3). In that case, I think we can use some kind of dp solution.
armahillo@reddit
If you're removing a suffix of length N and prepending it, can N > 1?
Plane_Pen_1520@reddit (OP)
No, maximum size of suffix you can remove is n-1
bravopapa99@reddit
Look up "Levenshtein distance", do some reading for inspiration!
https://en.wikipedia.org/wiki/Levenshtein_distance
_user1980@reddit
in c++ use stl deque class. use pop_back and push back function
_user1980@reddit
in c++ stl use deque. use pop_back and push_front functions.
ConfidentCollege5653@reddit
What part are you struggling with? What have you done so far?
Plane_Pen_1520@reddit (OP)
So what I did was:
I created a vector of maps of strings, v of size k+1. In this vector, v[i][str] gives the number of ways to arrive at string str using i operations.
I also created a queue of pair of strings and ints. My intuition was, I'll. check the top element of the queue which will have the string str and the number of operations current_operations to get to that string (Initially adding Src and 0). Then for each new_string that can be created from this string using operations, I simply add V[current_operations][str] to it. Also, I checked if V[current_operations+1][new_string] is equal to 0, If it is, then I add it to the queue.
ConfidentCollege5653@reddit
Can you share the code and then failing test case?
Intuitively this sounds like it can be simpler. I think you should be able to do this with just a queue.
Plane_Pen_1520@reddit (OP)
The test cases were hidden
ConfidentCollege5653@reddit
Can you share the code?
Low-Afternoon-636@reddit
I'm also wondering the same btw I'm new as well but I feel like I can probably do this.