We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Special String Again
  2. Discussions

Special String Again

  • circlespainter
     + 0 comments

    Super-cool! I used it (together with some luck that allowed me to find more small and meaningful test cases) to debug a similar idea I had, only that it works strictly forward rather than expanding from the middle:

        static long substrCount(final int n, final String s) {
        long specials = n;

        int i = 0, j = 1;
        while (j < n) {
            if (s.charAt(i) != s.charAt(j)) { // Different char and maybe middle char of special substring
                final int repeatedCharStringLen = j - i;

                // All len 2+ substrings of same-char string with fixed start are special
                specials += repeatedCharStringLen - 1;

                // If there is a mirrored same-char substring after the different char, then special
                final int newStringAfterSpecialIdx = j + 1 + repeatedCharStringLen;
                if (j + 1 < n &&
                    newStringAfterSpecialIdx <= n &&
                    s.substring(i, j).equals(s.substring(j + 1, newStringAfterSpecialIdx))) {

                    specials++;
                }

                // Advance
                i++;
                j = i;
            }

            // Expand substring to the right
            j++;
        }

        specials += substringsInLen(j - i) - (j - i); // All len 2+ substrings

        return specials;
    }

    private static long substringsInLen(final int len) {
        if (len <= 0)
            return 0;

        return len * (len + 1) / 2;
    }