Java Problem Solving #1: Anagram/String Permutation Check

Assalam Alaikum, and welcome to Solutions Nerd. In this video, we'll solve a Java problem efficiently. Let's get started!

I've begun a playlist where I'll upload problem solutions using Java. You can adapt these solutions to your preferred programming language.

Problem Overview

We have two strings:

• String A: "apple" (a common fruit name)
• String B: "alpep" (appears to be an anagram of "apple" with rearranged letters)

We need to determine if these two strings contain the same characters and are permutations of each other.

Solution Approach

We'll solve this without using complex data structures or algorithms. Here's our strategy:

1. Create a result string to store matched characters
2. Use nested loops to compare characters
3. Track used indexes to avoid reusing the same character

Implementation Steps

// Initialize result string
String result = "";
// Track indexes we've already matched
ArrayList indexes = new ArrayList();
// Outer loop: iterate through string A
for (int i = 0; i < A.length(); i++) {
    // Inner loop: search for current character in string B
    for (int j = 0; j < B.length(); j++) {
        // Skip already used indexes
        if (!indexes.isEmpty() && indexes.contains(j)) continue;
        // Check if characters match
        if (A.charAt(i) == B.charAt(j)) {
            result = result + B.charAt(j);
            indexes.add(j);
            break;
        }
    }
}

How It Works

Let's trace through the execution:

1. First iteration (i=0): Finds 'a' at index 0 in B → adds to result
2. Second iteration (i=1): Finds first 'p' at index 2 in B → adds to result
3. Third iteration (i=2): Finds second 'p' at index 4 in B (skips index 2 since it's already used)
4. Fourth iteration (i=3): Finds 'l' at index 1 in B → adds to result
5. Fifth iteration (i=4): Finds 'e' at index 3 in B → adds to result

Verification

After sorting both strings and comparing them (or by checking if the result equals the original string after sorting), we can confirm they're anagrams.

Time Complexity

This solution has O(n²) time complexity due to nested loops, where n is the string length. For more efficiency, consider:

• Sorting both strings and comparing (O(n log n))
• Using character frequency counting (O(n))

Hope you found this solution helpful! If you have any questions, please comment below. If you're new to the channel, consider subscribing. Thanks for watching!