recover.py

# Codewars - Recover a secret string from random triplets

import operator

class Node():
    def __init__(self, letter):
        self.letter = letter
        self.followers = set()
        self.all_following_nodes = None
    def add_follower(self, node):
        if node not in self.followers:
            self.followers.add(node)
    def __eq__(self, other):
        return self.letter == other.letter

def recoverSecret(triplets):
  'triplets is a list of triplets from the secrent string. Return the string.'
  letters = dict()
  for triplet in triplets:
      for index, letter in enumerate(triplet):
          if letter not in letters:
              letters[letter] = Node(letter)
          for follower in triplet[index+1 :]:
              letters.get(letter).add_follower(follower)
  
  letter_count = len(letters)
  result = [None] * letter_count
  
  for letter in letters:
      following_count = count_all_following_nodes(letter, letters)
      result[letter_count - following_count - 1] = letter
      
  return ''.join(result)

  
def count_all_following_nodes(letter, letters):
    current_node = letters[letter]
    if current_node.all_following_nodes:
        return current_node.all_following_nodes
    max_followers = 0
    for follower in current_node.followers:
        result = 1 + count_all_following_nodes(follower, letters)
        max_followers = result if result > max_followers else max_followers
    current_node.all_following_nodes = max_followers
    return max_followers