Given a string S of size N consisting of lowercase characters, the task is to find the sum of Manhattan distance between each pair (i, j) such that i?j and S[j] = S[i].
Examples:
Input: S = “ababa”
Output: 10
Explanation: The pairs having same characters are: (1, 3), (1, 5), (2, 4) and (3, 5). Therefore, the sum of Manhattan distance will be |3 – 1| + |5 – 1| + |4 – 2| + |5 – 3| = 10Input: S = “abc”
Output: 0
Naive Approach: The simplest approach is to generate all pairs (i, j) using two nested loops and check for each pair, whether it satisfies the given condition or not. If found to be true, add their distances to the answer. After checking all the pairs, print the answer.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The approach is similar to finding the Sum of Manhattan distances between all pairs of points. Follow the steps below to solve the problem:
- Initialize a variable ans as 0 to store the required result.
- Create a vector, V for each character to store the positions of each character separately.
- Traverse the string, S, and append the position of each character in their respective vector, V.
- Now, the problem is reduced to finding the sum of the Manhattan distance between each pair of points for each vector array.
- Iterate in the range [0, 25] using the variable i
- Store the sum of all the elements present in the vector, V[i] in a variable sum.
- Traverse the vector, V[i] using the variable j
- Subtract the value of V[i][j] from sum.
- Add the value sum – V[i][j] * (V[i].size() – 1 – j) to ans.
- Print the value of ans as the result.
Let the elements of the vector be x1, x2, x3, x4 which represents the indices of the same character.
This character will contribute value = |x2 – x1| + |x3 – x1| + |x4 – x1| + |x3 – x2| + | x4 – x2| + |x4 – x3|For a sorted array, this can also be written as (x2 + x3 + x4) – 3*x1 + (x3 + x4) – 2*x2 + (x4) – 1*x3.
Now, the sum can also be expressed as ?suffix[i + 1] – (n-i)*xi for i = 1 to n.
where suffix[i+1] is sum of elements from [i+1, n].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the sum of the manhattan// distances between same characters in stringvoid SumofDistances(string s){ // Vector to store indices for each // unique character of the string vector<int> v[26]; // Append the position of each character // in their respective vectors for (int i = 0; i < s.size(); i++) { v[s[i] - 'a'].push_back(i); } // Store the required result int ans = 0; // Iterate over all the characters for (int i = 0; i < 26; i++) { int sum = 0; // Calculate sum of all elements // present in the vector for (int j = 0; j < v[i].size(); j++) { sum += v[i][j]; } // Traverse the current vector for (int j = 0; j < v[i].size(); j++) { // Find suffix[i+1] sum -= v[i][j]; // Adding distance of all pairs // whose first element is i and // second element belongs to [i+1, n] ans += (sum - (v[i].size() - 1 - j) * (v[i][j])); } } // Print the result cout << ans;}// Driver Codeint main(){ // Given Input string s = "ababa"; // Function Call SumofDistances(s); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{ // Function to find the sum of the manhattan// distances between same characters in stringstatic void SumofDistances(String s){ // Vector to store indices for each // unique character of the string ArrayList<ArrayList<Integer>> v = new ArrayList<>(); for(int i = 0; i < 26; i++) v.add(new ArrayList<>()); // Append the position of each character // in their respective vectors for(int i = 0; i < s.length(); i++) { v.get(s.charAt(i) - 'a').add(i); } // Store the required result int ans = 0; // Iterate over all the characters for(int i = 0; i < 26; i++) { int sum = 0; // Calculate sum of all elements // present in the vector for(int j = 0; j < v.get(i).size(); j++) { sum += v.get(i).get(j); } // Traverse the current vector for(int j = 0; j < v.get(i).size(); j++) { // Find suffix[i+1] sum -= v.get(i).get(j); // Adding distance of all pairs // whose first element is i and // second element belongs to [i+1, n] ans += (sum - (v.get(i).size() - 1 - j) * (v.get(i).get(j))); } } // Print the result System.out.println(ans);}// Driver codepublic static void main(String[] args){ // Given Input String s = "ababa"; // Function Call SumofDistances(s);}}// This code is contributed by offbeat |
Python3
# Python program for the above approach#Function to find the sum of the manhattan#distances between same characters in stringdef SumofDistances(s): # Vector to store indices for each # unique character of the string v = [[] for i in range(26)] # Append the position of each character # in their respective vectors for i in range(len(s)): v[ord(s[i]) - ord('a')].append(i) # Store the required result ans = 0 # Iterate over all the characters for i in range(26): sum = 0 # Calculate sum of all elements # present in the vector for j in range(len(v[i])): sum += v[i][j] # Traverse the current vector for j in range(len(v[i])): # Find suffix[i+1] sum -= v[i][j] # Adding distance of all pairs # whose first element is i and # second element belongs to [i+1, n] ans += (sum - (len(v[i]) - 1 - j) * (v[i][j])) # Print the result print (ans)# Driver Codeif __name__ == '__main__': # Given Input s = "ababa" # Function Call SumofDistances(s)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the sum of the manhattan// distances between same characters in stringstatic void SumofDistances(string s){ // Vector to store indices for each // unique character of the string List<int>[] v = new List<int>[26]; for(int i = 0; i < 26; i++) v[i] = new List<int>(); // Append the position of each character // in their respective vectors for(int i = 0; i < s.Length; i++) { v[(int)s[i] - 97].Add(i); } // Store the required result int ans = 0; // Iterate over all the characters for(int i = 0; i < 26; i++) { int sum = 0; // Calculate sum of all elements // present in the vector for(int j = 0; j < v[i].Count; j++) { sum += v[i][j]; } // Traverse the current vector for(int j = 0; j < v[i].Count; j++) { // Find suffix[i+1] sum -= v[i][j]; // Adding distance of all pairs // whose first element is i and // second element belongs to [i+1, n] ans += (sum - (v[i].Count - 1 - j) * (v[i][j])); } } // Print the result Console.Write(ans);}// Driver Codepublic static void Main(){ // Given Input string s = "ababa"; // Function Call SumofDistances(s);}}// This code is contributed by ipg2016107 |
Javascript
<script>// Javascript program for the above approach// Function to find the sum of the manhattan// distances between same characters in stringfunction SumofDistances(s){ let v = []; for(let i = 0; i < 26; i++) v.push([]); // Append the position of each character // in their respective vectors for(let i = 0; i < s.length; i++) { v[s[i].charCodeAt(0) - 'a'.charCodeAt(0)].push(i); } // Store the required result let ans = 0; // Iterate over all the characters for(let i = 0; i < 26; i++) { let sum = 0; // Calculate sum of all elements // present in the vector for(let j = 0; j < v[i].length; j++) { sum += v[i][j]; } // Traverse the current vector for(let j = 0; j < v[i].length; j++) { // Find suffix[i+1] sum -= v[i][j]; // Adding distance of all pairs // whose first element is i and // second element belongs to [i+1, n] ans += (sum - (v[i].length - 1 - j) * (v[i][j])); } } // Print the result document.write(ans);}// Driver code// Given Inputlet s = "ababa";// Function CallSumofDistances(s);// This code is contributed by unknown2108</script> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
