29. ASCII Range Sum
✅ GFG solution to the ASCII Range Sum problem: find ASCII sum of characters between first and last occurrence of each character using efficient character tracking. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given a string s consisting of lowercase English letters, for every character whose first and last occurrences are at different positions, calculate the sum of ASCII values of characters strictly between its first and last occurrence.
Return all such non-zero sums (order does not matter).
📘 Examples
Example 1
Input: s = "abacab"
Output: [293, 294]
Explanation: characters 'a' and 'b' appear more than once:
'a' : between positions 1 and 5 → characters are b, a, c and ascii sum is 98 + 97 + 99 = 294.
'b' : between positions 2 and 6 → characters are a, c, a and ascii sum is 97 + 99 + 97 = 293.Example 2
Input: s = "acdac"
Output: [197, 199]
Explanation: characters 'a' and 'c' appear more than once:
'a' : between positions 1 and 4 → characters are c, d and ascii sum is 99 + 100 = 199.
'c' : between positions 2 and 5 → characters are d, a and ascii sum is 100 + 97 = 197.🔒 Constraints
$1 \le s.size() \le 10^5$
✅ My Approach
The optimal approach uses Character Position Tracking with Array Iteration to efficiently find first and last occurrences of each character and calculate ASCII sums:
Character Tracking + Range Sum Calculation
Initialize Variables:
Use a result vector to store non-zero ASCII sums.
For each character in the alphabet (a-z), track first and last positions.
Find Character Positions:
For each of the 26 lowercase letters, scan the string to find:
First occurrence position (
first)Last occurrence position (
last)
Calculate Range Sum:
If a character appears more than once (
last > first):Sum ASCII values of all characters between first and last positions (exclusive).
Add to result if sum is non-zero.
Process All Characters:
Repeat for all 26 letters to ensure no character is missed.
Return Result:
Return vector containing all non-zero ASCII sums.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(26 × n), where n is the length of the string. We iterate through the string 26 times (once for each letter) to find first and last occurrences, plus additional iterations for range sum calculations.
Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space for variables and the result vector (not counting output space).
🧑💻 Code (C++)
class Solution {
public:
vector<int> asciirange(string& s) {
vector<int> result;
int n = s.size();
for (int i = 0; i < 26; i++) {
int first = -1, last = -1;
for (int j = 0; j < n; j++) {
if (s[j] - 'a' == i) {
if (first == -1) first = j;
last = j;
}
}
if (first != -1 && last > first) {
int sum = 0;
for (int k = first + 1; k < last; k++) sum += s[k];
if (sum) result.push_back(sum);
}
}
return result;
}
};☕ Code (Java)
class Solution {
public ArrayList<Integer> asciirange(String s) {
ArrayList<Integer> result = new ArrayList<>();
int n = s.length();
for (int i = 0; i < 26; i++) {
int first = -1, last = -1;
for (int j = 0; j < n; j++) {
if (s.charAt(j) - 'a' == i) {
if (first == -1) first = j;
last = j;
}
}
if (first != -1 && last > first) {
int sum = 0;
for (int k = first + 1; k < last; k++)
sum += s.charAt(k);
if (sum != 0) result.add(sum);
}
}
return result;
}
}🐍 Code (Python)
class Solution:
def asciirange(self, s):
result = []
positions = {}
for i, char in enumerate(s):
if char not in positions:
positions[char] = [i, i]
else:
positions[char][1] = i
for char in sorted(positions.keys()):
first, last = positions[char]
if last > first:
total = sum(ord(s[j]) for j in range(first + 1, last))
if total:
result.append(total)
return result🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated