Find Subsequence in a String

Question

I have been solving this set of a challenge on Hackerrank, link : Hackerrank in a String

I have come up with my Algo which goes like this :

To check whether it has atleast two a's, r's and k's according to the hackerrank string

Check that it contains following chars h, a, c, k, e, r, n, k

let p[0], p(1), p[2].....,p[9] be the respective indices of h, a, c, k, e, r, r, a, n, k in string . If p[0] < p(1) < p[2] < .... < p[9] is true, then contains hackerrank.

I know is very bad, and the output is also not coming due to this error : Terminated due to timeout

CODE:

I have a method named hackerrankInString(String s), it returns "YES" or "NO" string

// Complete the hackerrankInString function below.
static String hackerrankInString(String s) {
  int countR = 0, countA = 0, countK = 0;
  //for reading multi-line inputs, it will perform operation individually 
  // on the inputs
  while(scanner.hasNextLine()){
    for(int i=0; i < s.length(); i++){
      if(s.charAt(i) == 'r')
        countR++;

      if(s.charAt(i) == 'a')
        countA++;

      if(s.charAt(i) == 'k')
        countK++;
    }

    //It should atleast have two As, two Rs, and two Ks
    if(countR >= 2 && countA >= 2 && countK >= 2){
      //If the string contains hackerrank
      if(s.contains(Character.toString('h')) && s.contains(Character.toString('a'))  && s.contains(Character.toString('c')) && s.contains(Character.toString('k')) && s.contains(Character.toString('e')) && s.contains(Character.toString('r')) &&    s.contains(Character.toString('n'))){
          if((s.indexOf('h') > s.indexOf('a')) && (s.indexOf('h') > s.indexOf('c')) && (s.indexOf('h') > s.indexOf('k')) && (s.indexOf('h') > s.indexOf('e')) && (s.indexOf('h') > s.indexOf('r')) && (s.indexOf('h') > s.lastIndexOf('r')) && (s.indexOf('h') > s.lastIndexOf('a')) && (s.indexOf('h') > s.indexOf('n')) && (s.indexOf('h') > s.lastIndexOf('k'))){
              if((s.indexOf('a') > s.indexOf('c')) && (s.indexOf('a') > s.indexOf('k')) && (s.indexOf('a') > s.indexOf('e')) && (s.indexOf('a') > s.indexOf('r')) && (s.indexOf('a') > s.lastIndexOf('r')) && (s.indexOf('a') > s.lastIndexOf('a')) && (s.indexOf('a') > s.indexOf('n')) && (s.indexOf('a') > s.lastIndexOf('k'))){
                  if((s.indexOf('c') > s.indexOf('k')) && (s.indexOf('c') > s.indexOf('e')) && (s.indexOf('c') > s.indexOf('r')) && (s.indexOf('c') > s.lastIndexOf('r')) && (s.indexOf('c') > s.lastIndexOf('a')) && (s.indexOf('c') > s.indexOf('n')) && (s.indexOf('c') > s.lastIndexOf('k'))){
                      if((s.indexOf('k') > s.indexOf('e')) && (s.indexOf('k') > s.indexOf('r')) && (s.indexOf('k') > s.lastIndexOf('r')) && (s.indexOf('k') > s.lastIndexOf('a')) && (s.indexOf('k') > s.indexOf('n')) && (s.indexOf('k') > s.lastIndexOf('k'))){
                        if((s.indexOf('e') > s.indexOf('r')) && (s.indexOf('e') > s.lastIndexOf('r')) && (s.indexOf('e') > s.lastIndexOf('a')) && (s.indexOf('e') > s.indexOf('n')) && (s.indexOf('e') > s.lastIndexOf('k'))){
                            if((s.indexOf('r') > s.lastIndexOf('r')) && (s.indexOf('r') > s.lastIndexOf('a')) && (s.indexOf('r') > s.indexOf('n')) && (s.indexOf('r') > s.lastIndexOf('k'))){
                                if((s.lastIndexOf('r') > s.lastIndexOf('a')) && (s.lastIndexOf('r') > s.indexOf('n')) && (s.lastIndexOf('r') > s.lastIndexOf('k'))){
                                    if((s.lastIndexOf('a') > s.indexOf('n')) && (s.lastIndexOf('a') > s.lastIndexOf('k'))){
                                        if(s.indexOf('n') > s.lastIndexOf('k')){
                                            return "YES";
                                        }
                                    }
                                }
                            }
                        }
                      }
                  }
              }
          }
        }
      }
    }

    return "NO";
}

Please help me with this, I want to learn two thigs,

How to solve this challenge
How to solve my third algo statement efficiently

Any help would be appreciated.

score 1 · Answer 1 · answered Apr 06 '19 at 09:54

Had not many time to check, but can look something like that

public static String solve(String startWord, String givenWord) {
    for(int i = 0; i < startWord.length(); i++) {
        String letter = startWord.substring(i, i + 1);
        int index = givenWord.indexOf(letter);
        if(index == -1) {
            return "NO";
        } else {
            givenWord = givenWord.substring(index + 1, givenWord.length());
        }
    }

    return "YES";
}

Nicholas K · Accepted Answer · 2019-04-06T11:07:10.900

1

You can make use of a regex to solve the problem:

static String hackerrankInString(String input) {
    final String regexHack = ".*h.*a.*c.*k.*e.*r.*r.*a.*n.*k.*";
    return input.matches(regexHack) ? "YES" : "NO";
}

Call it using :

System.out.println(hackerrankInString("hhaacckkekraraannk"));  // YES
System.out.println(hackerrankInString("hackerworld"));         // NO

You can try out the regex here.

edited Apr 06 '19 at 11:07

answered Apr 06 '19 at 10:57

Nicholas K

15,148
7
31
57

I found this solution suitable, but since I don't know how this works. Could you please provide a description of this works? I need to learn this technique, it will definitely help me in the long run. – Alok Apr 06 '19 at 12:39
If you click the link you will get an explanation for the regex on the right handside. Are you asking about *how* regex works or how the solution works with regex? – Nicholas K Apr 06 '19 at 12:41
**I'm asking both Nicholas.** It is just a simulator or an online regex expression checker. I really need to understand this stuff. Shall I start learning regex? – Alok Apr 06 '19 at 12:44
1

Regex is always helpful. In this answer, we are checking whether the input *String* matches the regex. In lay man terms the regex is just making sure that *your* String will contain at minimum `hackerrank`. If true, it return "YES" else it returns "FALSE". The `.*` matches anything that lies between `h`, `a`, `c`..... `n`, `k` – Nicholas K Apr 06 '19 at 12:47
Any good website to learn about regex **(for noobs)** Nicholas? – Alok Apr 06 '19 at 12:48
Plenty of sites online. [This SO question](https://stackoverflow.com/questions/4736/learning-regular-expressions) is also a good place to start. – Nicholas K Apr 06 '19 at 12:50
Yeah, will do in a moment. Just one more question, could you please tell me why every time we have done `*.` with every single word? – Alok Apr 06 '19 at 12:52
1

That is to denote that there can be *any* number of characters between *each* alphabet. You can play around with the regex in the link of the answer. – Nicholas K Apr 06 '19 at 12:55

Find Subsequence in a String

2 Answers2