In this post, we will solve Letter Islands HackerRank Solution. This problem (Letter Islands) is a part of HackerRank Problem Solving series.
Solution – Letter Islands – HackerRank Solution
Python
from collections import defaultdict
class LetterIslands:
def __init__(self):
self.s = 0
self.k = 0
self.n = 0
self.result = 0
def get_indice(self):
cache = defaultdict(list)
for (idx,let) in enumerate(self.s):
cache[let].append(idx)
for (key,val) in cache.items():
l = len(val)
if l < self.k:
continue
else:
for i in range(len(val)-1):
if val[i+1] - val[i] <= 1:
l -= 1
if l == self.k:
self.result += 1
return cache
def get_result(self):
for (let, pos) in self.get_indice().items():
len_ = 1
arr = [[let, pos]]
while len(arr) > 0:
dict_ = defaultdict(list)
temp = []
for t in arr:
for indice in t[1]:
try:
dict_[t[0] + self.s[indice + len_]].append(indice)
except:
pass
len_ = len_+1
for (key,val) in dict_.items():
l = len(val)
if l < self.k:
continue
else:
i = 0
lenVal = len(val)
while l >= self.k and i < lenVal-1:
if val[i+1] - val[i] <= len_:
l -= 1
i += 1
if l == self.k:
self.result += 1
if l >= self.k - 1:
temp.append([key,val])
arr = temp
return (self.result)
def debug(self):
try:
self.solve()
print(self.result)
except:
pass
def solve(self):
self._input()
self.get_result()
def _input(self):
self.s = input()
self.k = int(input())
self.n = len(self.s)
if __name__ == "__main__":
LetterIslands().debug()
Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
if(in.hasNext()){
final char[] str = in.next().toCharArray();
if(str.length>0 && in.hasNext()){
int k = in.nextInt();
if(k>0 && k<=str.length){
System.out.println((new FoundSubStrings(str, k)).count());
}
}
}
}
static class FoundSubStrings {
private final char[] str;
private final int k;
private Map<Long, SubString> curr;
private Map<Long, SubString> next;
private SubString previousSub=null;
private int previousSubParentStartIndex = -1;
private int previousSubLen = -1;
public FoundSubStrings(char[] str, int k) {
this.str = str;
this.k = k;
curr = new HashMap<>(str.length>32 ? str.length>>1 : str.length);
next = new HashMap<>(str.length>32 ? str.length>>1 : str.length);
}
public long count(){
long countResult = 0;
int startIndex;
char lastChar = str[0];
int lastCharCount = 0;
for(int i=0; i<=str.length; i++){
if(i==str.length || lastChar!=str[i]){
if(lastCharCount>1){
for(int j=i-lastCharCount; j<i-1; j++){
this.add(j, lastChar, i-j);
}
}
this.add(i-1, lastChar);
if(i!=str.length){
lastChar = str[i];
lastCharCount = 1;
}
} else {
lastCharCount++;
}
}
this.switchLists();
while(!curr.isEmpty()){
for(SubString subStr : curr.values()){
if(subStr.islands==k){
countResult++;
if(k==1 && subStr.size==1){
countResult+=str.length-subStr.startIndex-subStr.len;
continue;
}
} else if(subStr.size<k){
continue;
}
for(int i=0; i<subStr.size && ((startIndex=subStr.indexes[i])<(str.length-subStr.len)); i++){
this.add(subStr.startIndex, startIndex, str[startIndex+subStr.len], subStr.len+1, subStr.size);
}
}
this.switchLists();
}
return countResult;
}
private void add(int parentStartIndex, int startIndex, char chr, int len, int childsLength){
if(previousSubParentStartIndex!=parentStartIndex || previousSubLen!=len || previousSub.chr!=chr){
long key = getKey(parentStartIndex, len, chr);
previousSub = next.get(key);
if(previousSub==null){
previousSub = new SubString(parentStartIndex, startIndex, chr, len, childsLength);
next.put(key, previousSub);
}
previousSubParentStartIndex = previousSub.parentStartIndex;
previousSubLen = len;
}
previousSub.addIndex(startIndex);
}
private void add(int startIndex, char chr, int len){
long key = getKey(len, chr);
SubString sub = next.get(key);
if(sub==null){
sub = new SubString(startIndex, chr, len);
next.put(key, sub);
}
sub.addIndex(startIndex);
}
private void add(int startIndex, char chr){
if(previousSub==null || previousSubLen!=1 || previousSub.chr!=chr){
long key = getKey(chr);
previousSub = next.get(key);
if(previousSub==null){
previousSub = new SubString(startIndex, chr, 1);
next.put(key, previousSub);
}
previousSubLen = 1;
}
previousSub.addIndex(startIndex);
}
private void switchLists(){
previousSubParentStartIndex = -1;
previousSub = null;
Map<Long, SubString> tmp = curr;
curr = next;
next = tmp;
tmp.clear();
}
public static long getKey(int parentStartIndex, int length, char chr){
return (((long)parentStartIndex) | ((long)length<<31) | ((long)chr)<<23);
}
public static long getKey(int length, char chr){
return (((long)length<<31) | (((long)chr)<<23));
}
public static long getKey(char chr){
return (((long)chr)<<23);
}
class SubString implements Comparable<SubString> {
private final int parentStartIndex;
private final int len;
private final char chr;
private int startIndex;
private int islands = 0;
private int[] indexes;
private int size = 0;
public SubString(int startIndex, char chr, int length) {
this(-1, startIndex, chr, length, 16);
}
public SubString(int startIndex, char chr, int length, int childsLength) {
this(-1, startIndex, chr, length, childsLength);
}
public SubString(int parentStartIndex, int startIndex, char chr, int length, int childsLength) {
this.parentStartIndex = parentStartIndex;
this.startIndex = startIndex;
this.len = length;
this.chr = chr;
this.indexes = new int[childsLength>16? 16: childsLength+1];
}
public void addIndex(int index){
if(size==0 || (indexes[size-1]+len<index)){
islands++;
}
if(indexes.length==size+1){
int[] tmpArr = new int[indexes.length<<1];
System.arraycopy(indexes, 0, tmpArr, 0, indexes.length);
indexes = tmpArr;
}
indexes[size++] = index;
}
@Override
public int compareTo(SubString o) {
return (this.parentStartIndex==o.parentStartIndex) ? chr - o.chr :
this.parentStartIndex - o.parentStartIndex;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder(100);
sb.append("SubString{startIndex=").append(startIndex).append(", length=")
.append(len).append(", islands=")
.append(islands).append(", numberOfIndexes=")
.append(size).append(", arr=");
for(int i=startIndex; i<startIndex+len; i++){
sb.append(str[i]).append(',');
}
sb.setCharAt(sb.length()-1,'}');
return sb.toString();
}
}
}
}
Note: This problem (Letter Islands) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.