import java.util.*;


public class FriendCircles {

    public static int friendCircles(String[] friends) {
        int result = 0;
        if (friends == null || friends.length == 0) return result;

        int n = friends.length;
        boolean[][] visited = new boolean[n][n];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (friends[i].charAt(j) == 'Y' && !visited[i][j]) {
                    visitFriends(friends, visited, i, j);
                    result++;
                }
            }
        }

        return result;
    }

    private static void visitFriends(String[] friends, boolean[][] visited, int i, int j) {

        int n = friends.length;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * n + j);
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            int x = pos / n;
            int y = pos % n;

            //top
            if (x - 1 >= 0 && !visited[x - 1][y] && friends[x - 1].charAt(y) == 'Y') {
                queue.offer((x - 1) * n + y);
                visited[x - 1][y] = true;
            }


            //right
            if (y + 1 < n && !visited[x][y + 1] && friends[x].charAt(y + 1) == 'Y') {
                queue.offer(x * n + y + 1);
                visited[x][y + 1] = true;
            }


            //left
            if (y - 1 >= 0 && !visited[x][y - 1] && friends[x].charAt(y - 1) == 'Y') {
                queue.offer(x * n + y - 1);
                visited[x][y - 1] = true;
            }

            //down
            if (x + 1 < n && !visited[x + 1][y] && friends[x + 1].charAt(y) == 'Y') {
                queue.offer((x + 1) * n + y);
                visited[x + 1][y] = true;
            }
        }
    }

    public static void main(String[] args) {
        String[] test = {"YYNY","YYYN","NYYN","YNNY"};

        int result = friendCircles(test);
        System.out.println(result);
    }

}

import java.util.*;

public class StringChain {
    private static int longestChain(String[] input) {
        int max = 0;
        if (input == null || input.length == 0) return max;

        HashSet<String> set = new HashSet<>(Arrays.asList(input));
        HashSet<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        for (String str : input) {
            queue.offer(str);
            int count = 0;
            System.out.println("start: " + str);

            while (!queue.isEmpty()) {
                int size = queue.size(); 
                count++;
                for (int j = 0; j < size; j++) {
                    String s = queue.poll();

                    //try to delete every character
                    for (int i = 0; i < s.length(); ++i) {
                        StringBuilder sb = new StringBuilder(s);
                        sb.deleteCharAt(i);
                        System.out.println(sb.toString());
                        if (set.contains(sb.toString()) && !visited.contains(sb.toString())) {
                            queue.offer(sb.toString());
                            visited.add(sb.toString());
                        }
                    }
                }
            }

            max = Math.max(max, count);
            visited.clear();
        }

        return max;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] test = {"a","b","ba","bca","bda","bdca"};
        int result = longestChain(test);
        System.out.println(result);
    }



}