- Special String Again
- Discussions
Special String Again
Special String Again
+ 61 comments Really simple 3 pass solution: 1. Build a list of tuples such that the string "aaabbc" can be squashed down to [("a", 3), ("b", 2), ("c", 1)]. 2. add to answer all combinations of substrings from these tuples which would represent palindromes which have all same letters. 3. traverse this list to specifically find the second case mentioned in probelm
Here is my code:
def substrCount(n, s): l = [] count = 0 cur = None # 1st pass for i in range(n): if s[i] == cur: count += 1 else: if cur is not None: l.append((cur, count)) cur = s[i] count = 1 l.append((cur, count)) ans = 0 # 2nd pass for i in l: ans += (i[1] * (i[1] + 1)) // 2 # 3rd pass for i in range(1, len(l) - 1): if l[i - 1][0] == l[i + 1][0] and l[i][1] == 1: ans += min(l[i - 1][1], l[i + 1][1]) return ans
+ 15 comments The hardest part, was getting my brain to refocus on this "Special Palindrone" definition. Originally I was coding for a normal palindrone, which is VASTLY different and more complicated. Once I wasted time on that and re-read the problem, the solution wasn't too difficult.
My Solution: C#
static long substrCount(string s) { long retVal = s.Length; for (int i = 0; i < s.Length; i++) { var startChar = s[i]; int diffCharIdx = -1; for (int j = i + 1; j < s.Length; j++) { var currChar = s[j]; if (startChar == currChar) { if ((diffCharIdx == -1) || (j - diffCharIdx) == (diffCharIdx - i)) retVal++; } else { if (diffCharIdx == -1) diffCharIdx = j; else break; } } } return retVal; }
+ 1 comment The testcases for this are very disappointing. There's only 3 test cases that are human-parsable. There should be more than this.
The custom testcase I used that found the error I had in my code despite passing the 3 human-parsable test cases:
7 aaabaaa
(should be 16)
+ 3 comments Java 8
Passed all test cases
static long substrCount(int n, String s) { // initialize counter to n because each character is a // palindromic string int counter = n; // to count consecutive characters that are the same int consec = 1; // the middle index of a 3-character symmetry, // assigned only once detected int midIndex = -1; // compare with previous character so start with i=1 for (int i = 1; i < n; i++) { if (s.charAt(i) == s.charAt(i-1)) { // Condition 1: All of the characters are the same // For n consecutive characters that are the same, // we have this formula: // Number of palindromic strings = // (n-1) + (n-2) + ... + (n-(n-1)) counter += consec; consec++; // Condition 2: All characters except the middle one // are the same if (midIndex > 0) { // check for symmetry on both sides // of the midIndex if ((midIndex-consec) > 0 && s.charAt(midIndex-consec) == s.charAt(i)) { counter++; } else { // no more possibility of palindromic string // with this midIndex midIndex = -1; } } } else { // reset consecutive chars counter to 1 consec = 1; // check for a 3-character symmetry if (((i-2) >= 0) && s.charAt(i-2) == s.charAt(i)) { counter++; // 3-char symmetry is detected // to check if the next characters are the same // and symmetrical along the midIndex midIndex = i-1; } else { midIndex = -1; } } } return counter; }
+ 8 comments Here's a really simple solution for Python3:
def substrCount(n, s): count = n for x in range(n): y = x while y < n - 1: y += 1 if s[x] == s[y]: count += 1 else: if s[x:y] == s[y+1:2*y-x+1]: count += 1 break return count
Sort 736 Discussions, By:
Please Login in order to post a comment