We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. String Reduction
  5. Discussions

String Reduction

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 61 Discussions, By:

votes

Please Login in order to post a comment

  • kwang42
    8 years ago+ 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.

    19|
    Permalink
    View more Comments..
  • gabrielfair
    6 years ago+ 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'

    7|
    Permalink
  • peteryar19
    1 month ago+ 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|
    Permalink
  • peteryar19
    5 months ago+ 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|
    Permalink
  • dallas88
    5 months ago+ 0 comments

    Simple for everyone who know math. Medium for all others. Not HARD

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature