Sum of Manhattan distances between repetitions in a String | Java program for the above approach ; Function to find the sum of the manhattan distances between same characters in string ; Vector to store indices for each unique character of the string ; Append the position of each character in their respective vectors ; Store the required result ; Iterate over all the characters ; Calculate sum of all elements present in the vector ; Traverse the current vector ; Find suffix [ i + 1 ] ; Adding distance of all pairs whose first element is i and second element belongs to [ i + 1 , n ] ; Print the result ; Driver code ; Given Input ; Function Call
import java . lang . * ; import java . util . * ; class GFG { static void SumofDistances ( String s ) { ArrayList < ArrayList < Integer > > v = new ArrayList < > ( ) ; for ( int i = 0 ; i < 26 ; i ++ ) v . add ( new ArrayList < > ( ) ) ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { v . get ( s . charAt ( i ) - ' a ' ) . add ( i ) ; } int ans = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { int sum = 0 ; for ( int j = 0 ; j < v . get ( i ) . size ( ) ; j ++ ) { sum += v . get ( i ) . get ( j ) ; } for ( int j = 0 ; j < v . get ( i ) . size ( ) ; j ++ ) { sum -= v . get ( i ) . get ( j ) ; ans += ( sum - ( v . get ( i ) . size ( ) - 1 - j ) * ( v . get ( i ) . get ( j ) ) ) ; } } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { String s = " ababa " ; SumofDistances ( s ) ; } }