Counting Equal Pairs in a String in Java

To determine the number of equal pairs in a string, locate all instances where the same characters appear in various locations inside the text. A pair is deemed "equal" if two characters are identical but appear at separate indices. The aim is to determine how many such pairings appear in the string.

Understanding the Problem

Identify all letter pairings in a string that are equivalent but have different indices. For example, in the string "abba", the letters 'a' appear at indices 0 and, it would result in one equal pair.

Notation: Denote the string as s. - A pair is represented by (i, j), where s[i] == s[j], and i< j.

Brute-Force Approach:

• The easiest solution is to employ nested loops.
• The outer loop iterates through every character in the string.
• The inner loop searches for matches between all consecutive characters.

The temporal complexity of this technique is O(n^2), where n is the length of the string.

Example 1: "Abba"

1. Enter "abba".
2. Pairs:
   
   • Compare the character at index 0 ('a') to characters at successive indices (1, 2, 3).
     
     1. 'a' at index zero and 'b' at index one are not equivalent.
     2. 'a' at index zero and 'b' at index two are not equivalent.
     3. 'a' at index 0 and 'a' at index 3 form an equal pair.
   • Compare the character at index 1 ('b') with the following indices:
     
     1. 'b' at index 1 and 'b' at index 2 form an equal pair.
     2. 'b' at index one and 'a' at index three are not equivalent.
   • Compare the character at index 2 ('b') with the following indices:
     
     1. 'b' at index two and 'a' at index three are not equivalent.
3. Result: There are two equal pairs: (0, 3) and (1, 2).

Example 2: "abcd"

1. Enter "abcd".
2. Pairs:
   
   • 'a' at index 0 does not match subsequent indices.
   • 'b' at index 1 does not match in consecutive indices.
   • 'c' at index 2 does not match any following indices.
   • There are no consecutive characters after 'd' at index 3.
3. As a result, no pairings are equivalent.

File Name: EqualPairs.java

Output:

 2 

Optimized Approach Using HashMap

The brute-force method can be inefficient for large strings due to its quadratic time complexity. We can improve it by using a hashmap (or dictionary) to monitor the occurrences of each character as we cycle over the string. This method works as follows:

1. Create a dictionary that stores the count of each character.
2. Loop over the string, updating the dictionary as you go.
3. Add each character's count (so far seen) to the overall count of pairs.

This approach lowers the temporal complexity to (O(n)).

File Name: EqualPairsOptimized.java

Output:

 2 

Conclusion

Counting equal pairs in a string requires finding all character matches at different indices. The brute-force method works well for short strings, but for larger strings, an improved approach using a hash map is more efficient. Understanding both tactics enables you to choose the best one based on the situation and requirements.