# Checking that all occurrences of 'g' have another 'g' as a neighbor

We'll say that a lowercase 'g' in a string is "happy" if there is another 'g' immediately to its left or right. Return true if all the g's in the given string are happy.

gHappy("xxggxx") → true
gHappy("xxgxx") → false
gHappy("xxggyygxx") → false


This is my code so far, which I think is very messy.

  public boolean gHappy(String str)
{
for(int i=1;i<str.length()-1;i++)
{
if(str.charAt(i)=='g')
if(str.charAt(i-1)!='g'&&str.charAt(i+1)!='g')
return false;
}
if(str.length()==1)
return false;
if(str.equals(""))
return true;
if(str.charAt(str.length()-1)=='g')
if(str.charAt(str.length()-2)!='g')
return false;

return true;
}


Other answers have good input on a number of factors I agree with, especially about the early-return logic, the bugs that were pointed out, and the bracing strategies.

My suggestion though, is to use a different (the right?) tool for the job.

Regular expressions are a tool that are designed for text processing, and a well-crafted expression is typically faster and more concise than the hand-coded alternative. Regular expressions are not always the solution, but in this case, the result would be simpler to read (for someone familiar with them).

In this case, the logic requires checking that all 'g' chars are happy for the check to return true. Alternatively, to make sure there are no unhappy 'g' chars.

The expression to check for unhappy 'g' chars will be:

 private static final Pattern UNHAPPYG = Pattern.compile("(?<!g)g(?!g)");


That expression says "Match any 'g' that has no 'g' before it, and no 'g' after it.

Then, you can use it as:

private static final boolean gHappy(String str) {
return !UNHAPPYG.matcher(str).find();
}


I have put together an Ideone example here.

• A counterpoint to using a Regex. One can easily step through an array of chars counting lengths of strings of gs and returning false if such a string has a length of one. A Regex is overkill. This string (?<!g)g(?!g) seems incredibly complicated for a problem so simply defined. – user2023861 Dec 2 '14 at 15:41

Since the empty string is happy, a string with a single non-g should also be happy. So instead of:

  if(str.length()==1)
return false;


It should be:

  if(str.length()==1)
return str.charAt(0) != 'g';


The code would be less messy if you used an IDE that can format the code nicely for you. For example in Eclipse, you could press Control Shift f to automatically reformat the code nicely.

A better way to check if a string is empty is using the isEmpty() method, instead of equals("").

I would find it easier to work with a char[] instead of making charAt calls.

Instead of hard-coding 'g', the method begs for generalization to work with any letter.

Applying the above, and the simplified loop suggested by @thepace, the code becomes:

public boolean gHappy(String str) {
return isHappyChar(str, 'g');
}

public boolean isHappyChar(String str, char c) {
if (str.isEmpty()) {
return true;
}
char[] letters = str.toCharArray();
if (letters.length == 1) {
return letters[0] != c;
}
for (int i = 1; i < letters.length - 1; i++) {
char x = letters[i];
if (x == c) {
char prev = letters[i - 1];
char next = letters[i + 1];
if (prev != c && next != c) {
return false;
}
}
}
// check for lonely "g" at the end or start
if (letters[letters.length - 1] == c && letters[letters.length - 2] != c
|| letters[0] == c && letters[1] != c) {
return false;
}

return true;
}


If you are using an IDE like Eclipse/IntelliJ/NetBeans, it's good to add unit tests to make it easy to verify your examples. Simply right-click inside your class, and look for a menu option to create tests. The IDE will create a basic test class that is runnable. Here are some example test cases using JUnit4 to verify the function works:

@Test
public void testEmpty() {
assertTrue(gHappy(""));
}

@Test
public void testSingleLetterG() {
assertFalse(gHappy("g"));
}

@Test
public void testSingleLetterNotG() {
assertTrue(gHappy("x"));
}

@Test
public void testTwoLetters() {
assertTrue(gHappy("gg"));
assertTrue(gHappy("aa"));
}

@Test
public void testExamples() {
assertTrue(gHappy("xxggxx"));
assertFalse(gHappy("xxgxx"));
assertFalse(gHappy("xxggyygxx"));
}

@Test
public void testLonelyLastG() {
assertFalse(gHappy("abcg"));
}

@Test
public void testLonelyFirstG() {
assertFalse(gHappy("gabc"));
}

@Test
public void test_gggaaa() {
assertTrue(gHappy("gggaaa"));
}

• I think this returns false for "gggaaa". – JS1 Dec 1 '14 at 8:29
• @JS1 well-spotted, fixed now. Also added a test case for it. – janos Dec 1 '14 at 9:05
• Now you are indexing [-1] if the first character is 'g'. Sorry I'm not trying to pick on you or anything, just letting you know. – JS1 Dec 1 '14 at 9:10
• @JS1 Argh, copy paste mistake... Fixed it, and it's really good you pointed out, thanks for that! – janos Dec 1 '14 at 9:34

I'll make a few remarks before addressing the algorithm:

• Don't omit the optional braces: the maintenance pitfall is just not worth the space savings. Especially since the indentation is such a mess.
• This is a pure function that does not rely on any object state. As such, it should probably be declared static.
• Somespacesforreadabilitywouldbegood. There isn't a single space in all of this line:

if(str.charAt(i-1)!='g'&&str.charAt(i+1)!='g')


Generally, you should put a space before and after each binary operator, a space after any comma or semicolon, and a space after keywords such as if.

I agree that having all of those special cases is messy. In fact, I would say that one of them (if(str.length()==1) return false;) is not correct, if the string consists of just a single letter other than 'g'. After all, you return true for an empty string — why not also return true for "x"?

I would start by eliminating all special cases…

public static boolean gHappy(String str) {
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'g') {
// TODO: This crashes if 'g' occurs at the beginning or end
if (str.charAt(i - 1) != 'g' && str.charAt(i + 1) != 'g') {
return false;
}
}
}
return true;
}


Then fix the crashes by checking for out-of-bounds indexes just before trying to call .charAt().

public static boolean gHappy(String str) {
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == 'g') {
if ( (i == 0                || str.charAt(i - 1) != 'g') &&
(i == str.length() - 1 || str.charAt(i + 1) != 'g')) {
return false;
}
}
}
return true;
}


Then it's clear that an initial 'g' is treated as one that has no neighboring 'g' to its left, and a final 'g' is treated as one that has no right neighbor.

I like @rolfl's idea of using regular expressions. His regex is not exactly simple though, and requires a bit of regex mastery (I like this tutorial about lookahead and lookbehind, for your information).

An alternative along the same lines is this simpler approach:

1. Remove all consecutive "g" letters, that is, /gg+/ or in other words /g{2,}/
2. If the resulting string contains a "g", that must be a solitary "g", and as such our string is not happy

The implementation is simple:

private static final boolean gHappy(String str) {
return !str.replaceAll("gg+", "").contains("g");
}


This is simpler, but not as efficient as @rolfl's, because the regex is recompiled on every call. We can make it more efficient using a Pattern and compiling once:

private static final Pattern CONSECUTIVE_GS = Pattern.compile("gg+");

private static final boolean gHappy(String str) {
return !CONSECUTIVE_GS.matcher(str).replaceAll("").contains("g");
}


I'm quietly wondering which is more efficient: a regex with a lookahead + lookbehind, versus a simpler regex + .contains() call.

A few tips:

1. Validate the string for empty and blank before the loop.
2. Edge cases i.e str.length()==1 should also be before the loop.
3. If the edge case are a part of the actual flow, don't explicilty mention it i.e the last condition of str.charAt(str.length()-1)=='g' is not required because it would be covered in the for loop.
4. Avoid multiple return statements.
• @thepace, Concerning #4, read this programmers.stackexchange.com/questions/118703/… I think the OP's code is a good situation for multiple returns. – user2023861 Dec 1 '14 at 16:16
• To each his own :) Mix it well but avoid multiple conditional blocks. – thepace Dec 1 '14 at 16:43

I agree with @rofl and @janos that regex is an option to be considered. Though it may be too advanced for OP.

Here is how one can do it without lookahead/lookbehind and without additional steps:

public static boolean gHappy(String str) {
return Pattern.matches("(gg+|[^g])*", str);
}


Interpretation of the regex is intuitive -to me- : str consists of any mix of either a run of gs of length at least two or non-g characters.

The solution lays in the exact definition.

That the string is unhappy if there is any g-sequence of 1 g. A g-sequence being a maximal substring "ggg...ggg".

public static boolean gHappy(String str) {
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) == 'g') { // Start of a g sequence
boolean unhappy = true;  // 1 g means unhappy
++i;
while (i < str.length() && str.charAt(i) == 'g') {
unhappy = false; // More than one
++i;
}
if (unhappy) {
return false;
}
// i at non-g or str.length().
}
}
return true;
}


In your code boundary cases were handled (empty string, length 1), partly even wrong. This is a typical "mathematical" approach, but as you see above often not needed.

Then the original presentation of the problem had that devious "if left or right is also g" which can easily lead to double work, or at most considering one to the right, instead of all to the right.

P.S. There is an even nicer solution with i = str.indexOf('g', i);.