String Chain Formation Program in Java

In this article, we will solve the String Chain Formation problem, where we need to determine whether we can arrange a given array of strings in such a way that the last character of one string matches the first character of the next. This problem is commonly encountered in word puzzles, graph theory, and algorithmic challenges. We will explore an efficient graph-based approach and an alternative sorting-based method to check for a valid chain formation.

Understanding the Problem

Given an array of strings, determine whether it is possible to arrange them in a sequence such that the last character of one string matches the first character of the next string.

Example

Input:
String[] words = {“apple”, “elephant”, “tiger”, “rat”};

Output:
Possible Chain: [“apple”, “elephant”, “tiger”, “rat”]

Explanation:

  • "apple" ends with 'e', and "elephant" starts with 'e'.
  • "elephant" ends with 't', and "tiger" starts with 't'.
  • "tiger" ends with 'r', and "rat" starts with 'r'.
  • Since all words connect, a valid chain is possible.

Approach to Solve the Problem

  1. Build character mappings:
    • Store first and last characters of each word.
    • Use a HashMap to count occurrences of each starting and ending letter.
  2. Check Eulerian Path conditions:
    • A valid path exists if at most one character has +1 difference in start and end counts.
  3. Try forming a sequence using backtracking (DFS or Graph approach).

Java Implementation – Using Graph (Optimal Approach)

package com.javacodepoint.stringarray;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class StringChainFormation {

    // Method to check if the given words can form a valid chain
    public static boolean canFormStringChain(String[] words) {
        Map<Character, Integer> inDegree = new HashMap<>();
        Map<Character, Integer> outDegree = new HashMap<>();
        Map<Character, List<String>> adjacencyList = new HashMap<>();
        Set<Character> uniqueChars = new HashSet<>();

        // Build graph representation
        for (String word : words) {
            char first = word.charAt(0);
            char last = word.charAt(word.length() - 1);
            
            outDegree.put(first, outDegree.getOrDefault(first, 0) + 1);
            inDegree.put(last, inDegree.getOrDefault(last, 0) + 1);

            adjacencyList.computeIfAbsent(first, k -> new ArrayList<>()).add(word);
            uniqueChars.add(first);
            uniqueChars.add(last);
        }

        // Check Eulerian Path conditions
        int startCount = 0, endCount = 0;
        for (char c : uniqueChars) {
            int in = inDegree.getOrDefault(c, 0);
            int out = outDegree.getOrDefault(c, 0);

            if (out - in == 1) {
                startCount++;
            } else if (in - out == 1) {
                endCount++;
            } else if (in != out) {
                return false;
            }
        }

        return (startCount == 1 && endCount == 1) || (startCount == 0 && endCount == 0);
    }

    public static void main(String[] args) {
        String[] words = {"apple", "elephant", "tiger", "rat"};

        if (canFormStringChain(words)) {
            System.out.println("Yes, the words can form a valid chain.");
        } else {
            System.out.println("No, a valid chain cannot be formed.");
        }
    }
}

OUTPUT:
Yes, the words can form a valid chain.

Explanation of the Code

  1. Build a character frequency map:
    • Track how many times each character appears at the start and end of words.
    • Store adjacency lists of words grouped by their first letter.
  2. Check Eulerian Path conditions:
    • At most one character should have +1 outgoing edge.
    • At most one character should have +1 incoming edge.
    • All other characters should have equal in-degree and out-degree.
  3. Return true if conditions match, otherwise return false.

Alternative Approach: Using Simple Sorting (Less Efficient)

import java.util.Arrays;

public class SimpleStringChain {

    public static boolean canArrangeStrings(String[] words) {
        Arrays.sort(words); // Sort alphabetically (not always correct but helps)
        
        for (int i = 0; i < words.length - 1; i++) {
            if (words[i].charAt(words[i].length() - 1) != words[i + 1].charAt(0)) {
                return false; // Break if chain rule is not satisfied
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] words = {"apple", "elephant", "tiger", "rat"};

        if (canArrangeStrings(words)) {
            System.out.println("Yes, a valid chain can be formed.");
        } else {
            System.out.println("No, a valid chain cannot be formed.");
        }
    }
}

Conclusion

This problem is closely related to Eulerian Path in Graph Theory, where we check incoming and outgoing edges to determine if a path exists.

You can learn the Top 20 string array programs for interview preparation (Click here).

Java logical programs list

Java Basic Programs

  1. Java Hello world program
  2. Java Program to Add two Numbers
  3. Java Program to Subtract two Numbers
  4. Java Program to Multiply two Numbers
  5. Java Program to Check Whether a Number is Even or Odd.
  6. Check whether a character is a Vowel or Consonant.
  7. Java Program to find Average of Two Numbers
  8. Java Program to find Average of Three Numbers
  9. Java Program to find the Area of Square
  10. Java Program to Calculate Simple Interest
  11. Java Program to Calculate Compound Interest
  12. List of basic logical programs in Java
  13. How to print a Fibonacci series up to a given number in Java?
  14. How to calculate the factorial of a given number in java?
  15. How to check whether an integer number is a prime number or not in java?
  16. How to check whether a number is a perfect number or not in java?
  17. How to check whether a number is an Armstrong number or not in java?
  18. How to reverse a number in Java?
  19. How to check whether a number is a Palindrome number or not in Java?
  20. How to swap two numbers without using a third variable in Java?
  21. How to reverse a string without using the reverse() method in java?
  22. How to check whether a String is a Palindrome or not in java?
  23. How to count characters from the string in java?
  24. How to check if two strings are anagrams of each other?
  25. How to count the occurrence of the given character in a string in java?
  26. How to swap two strings without using the third variable in java?
  27. Searching Algorithms in Java with Examples

Java String Programs

  1. String length without using length() method.
  2. Count the Number of Vowels in a String.
  3. Swap two strings without using the third variable.
  4. Reverse a string without using the reverse() method.
  5. Reverse the words in a given string sentence
  6. Check whether a String is a Palindrome or not in Java.
  7. Count characters from the string in Java.
  8. Count the number of words in the String.
  9. Check if the two strings are anagrams of each other.
  10. Count the occurrence of the given character in a string.
  11. Find the Maximum Occurring Character in a String
  12. Find the First non-repeating Character in a given String
  13. Remove all Duplicates from a given String
  14. Remove a given character from the String
  15. Find the Sum of Digits in a String.
  16. Compare two Strings in Java.
  17. String Permutations Program in Java
  18. Combinations of String in Java

Java String Array Programs

  1. Find Palindrome Strings in an Array
  2. Count Vowels in Each String in the Array
  3. Find Duplicate Strings
  4. Find Strings of Maximum Length
  5. Find Strings Starting with a Vowel
  6. Find Strings Containing a Substring
  7. String Permutations in an Array
  8. Find Strings Ending with a Specific Character
  9. Find Strings Containing Only Numbers
  10. Remove Strings Containing a Substring
  11. Find the Longest Common Prefix in an Array
  12. Check for Unique Characters in an Array
  13. Concatenate Strings by Delimiter
  14. Split Strings by Delimiter
  15. Find Common Strings from Two Arrays
  16. Merge and Sort Two Arrays of Strings
  17. String Chain Formation
  18. Sort Strings Array Alphabetically

Java Pattern Printing Programs

  1. Star pattern programs [Tricks] in Java
  2. Top 30-star pattern programs in java
  3. Top 10 Number pattern programs in java
  4. Top 10 Character pattern programs in java
  5. Top 50 Pattern printing programs in java
  6. Pyramid Pattern.
  7. Diamond Pattern.
  8. Hollow Diamond Pattern.

Java Series Printing Programs

  1. Print a Fibonacci series
  2. Even Numbers Series
  3. Odd Numbers Series
  4. Square Numbers Series
  5. Cube Numbers Series
  6. Print Series 1,2,9,28,65
  7. Java Program to Print Series 1,2,5,10,17
  8. Java Program to Print Series 2,4,8,16,32

Java Array-Based Programs

  1. Find the Length of an Array
  2. Get Array Input
  3. Different Ways to Print an Array
  4. Print all Negative Elements in an Array.
  5. Find GCD of N Numbers
  6. Copy an Array
  7. Merge Two Arrays.
  8. Sum of Two Arrays.
  9. Print Odd/Even No. from an Array.
  10. Put Even and Odd Elements in 2 Separate Arrays
  11. Find the Sum of an Array
  12. Sum of Even Numbers in an Array.
  13. Average of Odd/Even Numbers in Array.
  14. Count Even and Odd numbers in Array
  15. Calculate Average Using Array
  16. Find the Smallest Number in an Array.
  17. Find the Largest Number in an Array.
  18. 2nd Largest Number in an Array.
  19. Remove duplicate elements in an Array.
  20. Remove odd numbers from an array Java.
  21. Add Element to Array in Java.
  22. Insert Element at Specific Position
  23. Remove Element From Array in Java
  24. Count Repeated Elements in an Array
  25. Compare Two Arrays in Java
  26. Reverse an Array in Java
  27. Searching in Java with Examples

Multi-Dimensional Array Programs

  1. Print Matrix or 2D Array.
  2. Read a Matrix from the User.
  3. Add the Two Matrices.
  4. Subtract the Two Matrices.
  5. Matrix Multiplication.
  6. Identity Matrix Program.
  7. Symmetric Matrix Program.
  8. Find the Transpose of a Matrix.
  9. Find the Smallest Element in a Matrix.
  10. Find the Largest Element in a Matrix.
  11. Search Matrix in Java.
  12. The sum of Diagonals of a Matrix.

Java Sorting Programs

  1. Selection Sort in Java
  2. Bubble Sort in Java
  3. Insertion Sort in Java
  4. Merge Sort in Java
  5. Quick Sort in Java
  6. Heap Sort in Java
  7. Arrays.sort() in Java with Examples
  8. Collections.sort() in Java with Examples

Java Searching Programs

  1. Linear Search in Java with Examples
  2. Binary Search in Java with Examples
  3. Fibonacci Search in Java with Examples
  4. Interpolation Search in Java Examples
  5. Exponential Search in Java Examples
  6. Jump Search in Java with Examples
  7. Ternary Search in Java with Examples

Java Conversion Programs

  1. Binary to Decimal
  2. Binary to Decimal using Recursion
  3. Decimal to Binary
  4. Decimal to Octal
  5. Decimal to Hexadecimal
  6. Fahrenheit to Celsius
  7. Celsius to Fahrenheit

Java Game Programs

  1. Tic-Tac-Toe Game in Java
  2. Hangman Game in Java
  3. Rock Paper Scissors Game in Java
  4. Number Guessing Game in Java
  5. Word Search Solver Game in Java
  6. Tower of Hanoi Game in Java

Java Miscellaneous Programs

  1. Generate Random String in Java
  2. Generating Random Numbers in Java
  3. Generating OTP in Java
  4. Secret Message Program in Java

Java Programs based on the Collection Framework

  1. ArrayList Manipulation: add, remove Elements, find size
  2. Write a Java program to reverse a List without using the built-in Collections.reverse() method.
  3. Find duplicate elements in an ArrayList
  4. Implement a Java program to sort an ArrayList of integer numbers.
  5. Implement a Java program to sort an ArrayList of custom objects based on a specific attribute.
  6. Create a stack using an ArrayList and implement push, pop, and peek operations.
  7. Convert an ArrayList of strings into a string array.
  8. Write a Java program to remove all elements from an ArrayList that are greater than a certain value.
  9. Write a Java program to remove duplicates from an ArrayList while preserving the original order.
  10. Write a Java program to find the common elements in two given ArrayLists.
  11. ArrayList partition into two separate lists of odd/even numbers.
  12. Write a program that extracts a sublist from an ArrayList, given a start and end index.
  13. Merge two sorted ArrayLists into a single sorted ArrayList.
  14. Find unique string in ArrayList with its frequency
  15. Write a program to swap the positions of two elements in an ArrayList given their indices.
  16. Write a program to Create a Custom LinkedList in Java
  17. Write a Java program for Basic Queue Implementation using LinkedList
  18. Write a Java program to create a PriorityQueue to manage a to-do list

Leave a Reply

Your email address will not be published. Required fields are marked *