_2743. Count Substrings Without Repeating Character.md

2743. Count Substrings Without Repeating Character

---

First completed : June 21, 2024

Last updated : June 21, 2024

---

Related Topics : Hash Table, String, Sliding Window

Acceptance Rate : 70.222 %

---

To see the question prompt, click the title.

Solutions

• m2743 Weekly Premium.py
• m2743.java

Python

m2743 Weekly Premium.py

''' Notes
    a	b	a		b		a		b			sum
    1
        1 + 1
            2 + 1 - (1)
                    2+1-(1oc)=2
                            2+1-1=2
                                    2+1-1=2
                                                11

    so 1 + previous - how many rightshifts?

    ab, ba --> 5 
    a, b --> 6
    total 11
'''


class Solution:
    def numberOfSpecialSubstrings(self, s: str) -> int:
        previousCase = [-1] * 26

        left = 0
        output = 0
        prevVal = 0

        for i, c in enumerate(s) :
            prev:int = previousCase[ord(c) - ord('a')]
            newVal = 1 + prevVal

            if prev != -1 and prev >= left:
                shifts = prev - left + 1
                left = prev + 1
                newVal -= shifts

            previousCase[ord(c) - ord('a')] = i
            output += newVal
            prevVal = newVal

        return output

Java

m2743.java

class Solution {
    public int numberOfSpecialSubstrings(String s) {
        int[] previousOccurances = new int[26];
        Arrays.fill(previousOccurances, -1);

        int left = 0;
        int output = 0;

        for (int i = 0; i < s.length(); i++) {
            int previousIndex = previousOccurances[s.charAt(i) - 'a'];
            int newVal = 1 + i - left;

            if (previousIndex != -1 && previousIndex >= left) {
                int shiftAmount = previousIndex - left + 1;
                left = previousIndex + 1;
                newVal -= shiftAmount;
            }

            previousOccurances[s.charAt(i) - 'a'] = i;
            output += newVal;
        }

        return output;

    }
}