I want to find the number of strings that are lexicographically smaller than A and has substring B NOTE: the length of the strings should be <= |A|.

e.g. A = "da" and B = "c" then answer = 29: {'c', 'ac', 'bc', cX}, where X is any alphabet. also, constraints are pretty low, 1 <= |B|,|A| <= 1000 Please help thanks.

Given a tree with n nodes and n-1 edges, each edge has an integer value that maps to a character from A to Z. For each shortest paths between nodes determine if the sequence of characters of edges encountered can be rearranged to to be palindrome. We are required to count the number of pairs of nodes such that their shortest path can be rearranged to palindrome. (1<=n<=10^5) and tree diameter is less than 1000. Any ideas given those constraints?