String Reduction
String Reduction
+ 6 comments No need to use DP. This is purely a math problem.
If a[] has only one kind of character, such as "cccc", the answer is strlen(a);
Else: answer is either 1 or 2. This can be proved by mathematical induction. It seems reordering the array does not change result.
+ 2 comments The wording of this problem is very poor. For example, "Take any two adjacent distinct characters.."
What does it mean to be adjacent? Are letters adjacent if they are next to each other in the english alphabet? Or does adjacent mean every two distinct characters next to each other in the input string? If so, how does the given example make sense: "For the second case, one optimal solution is: bcab -> aab -> ac ->b..." after aab-> ac, where does the 'c' character come from? It wasn't in the input of 'aab'
+ 0 comments function reduceString(s){ let p1 = 0; let p2 = 1; const getReducedChar = (st)=>{ let counter = {a:0, b:0, c:0}; for(let x of st){ counter[x]+=1 } for(let x in counter){ if(counter[x] == 0){ return x } } } while(s[p2]){ let char; if(s[p1] !== s[p2]){ char = s[p1]+s[p2]; let reducedChar = getReducedChar(char); s = s.substr(0, p1)+ reducedChar + s.substr(p2+1); p1=0; p2=1; }else{ p1+=1; p2+=1 } return s.length } **I am of the opinion that the above code should work, not sure why it's not passing all hackerrank tests, it honestly seem to me hackerrank written test cases for this problem is flawed. Anyone thinking I am wrong somewhere? Please correct me** return str.length; }
+ 0 comments Hi guys, I copied all the test cases and paste on the custom test input section accurately, all the result where the same expected result outputted by hackerrank. but don't know why my submission always failed, anyone experience something like this
function stringReduction(s) { let counter = {a:0, b:0, c:0} let p1 = 0; let p2 = 1; let exemptChar = ''; const getReducedChar = (counter)=>{ for(let x in counter){ if(counter[x] == 0){ return x } } } while(p2< s.length){ if(s[p1] == s[p2]){ exemptChar = exemptChar + s[p1]; p1+=1; p2+=1 s = exemptChar + s.substr(p1) }else{ counter[s[p1]] +=1; counter[s[p2]] +=1 let reducedChar = getReducedChar(counter); s = exemptChar + reducedChar + s.substr(p2+1) exemptChar = '' p1 = 0; p2 = 1; counter = {a:0, b:0, c:0} } } return s.length
}
+ 0 comments Simple for everyone who know math. Medium for all others. Not HARD
Sort 61 Discussions, By:
Please Login in order to post a comment