Longest Happy Prefix LeetCode solution in Java

1
class Solution {
2
  public String longestPrefix(String s) {
3
    int n = s.length();
4
    char arr[] = s.toCharArray();
5
    int lps[] = new int[n];
6
    for (int i = 1; i < n; i++) {
7
      int j = lps[i - 1]; // COMPARING ITS i WITH ITS PREV ELEMENT
8
      while (j > 0 && arr[j] != arr[i]) {
9
        j = lps[j - 1]; // DEACREASING TILL WE FIND ITS PREFIX WHICH IS EQUAL TO ITS SUFFIX
10
      }
11
      if (arr[j] == arr[i]) { // IF ITS PREV IS SAME AS CURRENT THEN INCREAMENT IT
12
        j++;
13
      }
14
      lps[i] = j; // SAVE WHATEVER THE VALUE IS
15
    }
16
    int j = lps[n - 1];
17
    StringBuilder sb = new StringBuilder();
18
    for (int i = 0; i < j; i++) {
19
      sb.append(arr[i]);
20
    }
21
    return sb.toString();
22
  }
23
}
24
/*
25
ALTERNATE
26

27
 for(int i=1;i<n;i++){
28
           if(arr[i]==arr[j]){ // IF SAME INCREASE IT
29
               lps[i]=++j;
30
           }else if(j>0){ // ELSE DEACREASE TILL WE ARE NOT FINDING IT
31
               j=lps[j-1];
32
               i--;
33
           }
34
       }
35
       return s.substring(0,j);
36

37
*/