## Amazon Interview Question

SDE1s**Country:**India

**Interview Type:**Written Test

```
static int min_coloring(int num , String s) {
int count =0;
char arr[] = s.toCharArray();
int i=1;
int currentInterval=1;
boolean isSubStringSizeMoreThanK=false;
while( i < arr.length){
if(arr[i] == arr[i-1] ){
currentInterval++;
}
if(arr[i] != arr[i-1] || i == arr.length - 1){
if(currentInterval < num){
count++;
}else{
isSubStringSizeMoreThanK=true;
count += (int)Math.ceil((double)currentInterval/num);
}
currentInterval =1;
}
i++;
}
if(isSubStringSizeMoreThanK){
return count;
}else{
return -1;
}
}
```

```
static int min_coloring(int num , String s) {
int count =0;
char arr[] = s.toCharArray();
int i=1;
int currentInterval=1;
boolean isFirst=false;
int isSubStringSizeMoreThanK=0;
while( i < arr.length){
if(arr[i] == arr[i-1] ){
currentInterval++;
}
if(arr[i] != arr[i-1] || i == arr.length - 1){
if(currentInterval < num){
count++;
}else{
if(i == currentInterval){
isFirst = true;
}
isSubStringSizeMoreThanK++;
count += (int)Math.ceil((double)currentInterval/num);
}
currentInterval =1;
}
i++;
}
if(isSubStringSizeMoreThanK > 0){
if(isSubStringSizeMoreThanK ==1 && isFirst){
count++;
}
return count;
}else{
return -1;
}
}
```

```
using namespace std;
bool isEligible(int k, const string& str) {
if(str.size() < k) return false;
char c1 = str.at(str.size()-1);
char c2 = str.at(str.size()-2);
char c3 = str.at(str.size()-3);
if(c1 == c2 && c1 == c3) return true;
return false;
}
int colour_iterative(int k, const string& str) {
if(!isEligible(k, str)) return -1;
int i=0, num =0;
while(i<str.size()) {
int color = 1;
int c = str.at(i);
while(i+color < str.size() && str.at(i+color) == c) ++color;
num += ceil((double)color/k);
i+=color;
}
return num;
}
```

- shkolyar November 30, 2017