Project Title Explanation:

The “abscdas” string is that the two A characters are furthest apart (the distance is 5) and the S characters are only 4 away.

  • This means that a character with a distance must appear at least twice

The “absdakueba” character appears three times, counting the distance between the two farthest as, so this still returns the A character.

Train of thought

  1. Start by creating a maxChar to store the current longest distance character, and maxLen to store the corresponding length.
  2. If the string is iterated, use HashSet to store the first occurrence of the character, when there is a conflict, it means that there is a repeated occurrence of the character, calculate the distance need to obtain two values:
  • First value: the position where the character first appears j (need to find a structure to store it, which I was struggling with at the time), thought of two methods:
  1. The first violent, direct indexOf(current character)- returns the location of the first occurrence. It takes time to search every time.
  2. The second option is to create an array int[256] (all characters are 256, Ascii) and store values as they appear. O(1).
  • Second value: the current occurrence of position I (this can be obtained directly)
  1. Use i-j to find the interval length curMaxLen for this repeated character. The curMaxLen is compared to maxLen, and if the new one is longer, the length is replaced, and maxChar is replaced with the current character.

In the code

// The input is String; Output char

import java.util.HashSet;

public class FindLongestDistanceCharPairs {
    public static char findLongestCharPairs(String str){
        if (str.length() <= 1) {
            return ' ';
        }
        int maxLen = 0;
        char maxChar = ' ';
        // Store the current array, which is used to remove the weight
        HashSet hashSet = new HashSet();

        // Index the first occurrence of a character, directly create a full character size array, a total of 256 characters.
        int[] firstIndex = new int[256];

        for(int i = 0; i < str.length(); i++){if(hashSet.add(str.charAt(i))){
                // Record the first occurrence of the character corresponding to the current I
                firstIndex[str.charAt(i)] = i;
            }else{
                // Insert failed, there is a conflict, again appear - "calculate the same two character interval length
                // The position where the conflicting character first appears is j
                int j = firstIndex[str.charAt(i)];
                int curMaxLen = i - j;

                if (maxLen < curMaxLen) {
                    maxLen = curMaxLen;
                    maxChar = str.charAt(i);
                }
            }
        }
        System.out.println(maxLen);
        return maxChar;

    }

    public static void main(String[] args) {
        String str = "abbacdisauhfiugiugcouiqwgdcpiqpiubqiuncidsaunbibvasidbcaqpoavj'qk[408507-25!@%#^%*%&(^()&+{{}}:LKKPHJOGOIUOPYHGIPb"; System.out.println(findLongestCharPairs(str)); }}Copy the code