String Anagrams
Ramayana — Valmiki's Hidden Verses — Finding All Anagrammatic Shlokas in the Great Epic
एकाक्षरः नाम-भेदः परन्तु अर्थः एकः। सर्वा स्थितयः यासु — ताः संग्रहे सत्यम्॥
*Different arrangements of the same letters, yet the same meaning. Collect all positions where they arise — that is the truth.*
The Story
Valmiki, after completing the Ramayana, discovered a fascinating mathematical property: certain sacred syllables of the epic, when rearranged, revealed hidden blessings. The syllable `p = "god"` (just three letters) had three anagrams: `"god"`, `"ogd"`, and `"dgo"`. Any arrangement of these three letters carried equal divine power.
The question posed by the celestial musicians Narada and Tumburu: in the full Ramayana scroll `s`, at which positions do all the anagrams of `p` appear? Return every starting index.
"For `s = "cbaebabacd"` and `p = "abc"`," Narada began, "the answer is positions [0, 6]."
"Position 0: `'cba'` — that is `c,b,a` — an anagram of `a,b,c`. Yes!" "Position 6: `'bac'` — that is `b,a,c` — an anagram. Yes!"
"This is the same as sw-10 (Permutation in a String)," Tumburu observed, "except instead of returning true at the first match, we collect ALL starting indices."
"Exactly," Valmiki confirmed. "Same fixed-window sliding technique, same frequency comparison — but we record every valid window, not just the first."
Narada traced the algorithm with `s="cbaebabacd"`, `p="abc"`:
**Initialize:** - pf (p's frequency): [0...0], pf['a'-'a']=1, pf['b'-'a']=1, pf['c'-'a']=1 - sf (s window frequency): initialized for first window s[0..2]="cba" sf['c'-'a']=1, sf['b'-'a']=1, sf['a'-'a']=1 - Arrays.equals(pf, sf)? YES! Add index 0 to result.
**Slide i=3 (add 'e', remove s[0]='c'):** - sf['e'-'a']++; sf['c'-'a']-- - sf = {a:1, b:1, e:1} vs pf = {a:1, b:1, c:1} → NOT equal
**Slide i=4 (add 'b', remove s[1]='b'):** - sf['b'-'a']++; sf['b'-'a']-- → net change 0 in 'b' Actually: add s[4]='b', remove s[1]='b': sf['b']++ then sf['b']-- → no net change - sf = {a:1, b:1, e:1} → NOT equal
**Slide i=5 (add 'a', remove s[2]='a'):** - Add 'a': sf['a']++ → sf['a']=2; Remove 'a': sf['a']-- → sf['a']=1 - sf = {a:1, b:1, e:1} → NOT equal
**Slide i=6 (add 'b', remove s[3]='e'):** - Add 'b': sf['b']=2; Remove 'e': sf['e']=0 - sf = {a:1, b:2} → NOT equal
**Slide i=7 (add 'a', remove s[4]='b'):** - Add 'a': sf['a']=2; Remove 'b': sf['b']=1 - sf = {a:2, b:1} → NOT equal
**Slide i=8 (add 'c', remove s[5]='a'):** - Add 'c': sf['c']=1; Remove 'a': sf['a']=1 - sf = {a:1, b:1, c:1} == pf → YES! Add index 8-3+1=6 to result.
**Slide i=9 (add 'd', remove s[6]='b'):** - Add 'd': sf['d']=1; Remove 'b': sf['b']=0 - sf = {a:1, c:1, d:1} → NOT equal
Result: [0, 6] ✓
"Every position in the Ramayana scroll where a hidden blessing of `'abc'` is encoded has been found," Valmiki said, unrolling the complete list. "Position 0 and position 6."
Narada and Tumburu played their veenas in celebration. The hidden anagrammatic blessings of the Ramayana had been catalogued — every instance where the divine syllables appeared in rearranged form, carrying equal spiritual potency.
"The only difference from sw-10," Valmiki summarized, "is that we collect all valid windows instead of stopping at the first. The mechanism is identical: fixed window, frequency comparison, O(1) per slide."
This is the fixed Sliding Window for finding all anagram positions in a string.
Narada's First Instinct
For every window of size p.length(), check if its character frequency matches p's. Collect all matching start indices. O(n × m) time from the frequency comparison at each position.
public List<Integer> findAnagramsBruteForce(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] pFreq = new int[26];
for (char c : p.toCharArray()) pFreq[c - 'a']++;
for (int i = 0; i <= s.length() - p.length(); i++) {
int[] windowFreq = new int[26];
for (int j = i; j < i + p.length(); j++) {
windowFreq[s.charAt(j) - 'a']++;
}
if (Arrays.equals(pFreq, windowFreq)) {
result.add(i);
}
}
return result;
}Valmiki's Wisdom
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
int[] pf = new int[26]; // p's frequency
int[] sf = new int[26]; // Current window's frequency
// Build p's frequency
for (char c : p.toCharArray()) pf[c - 'a']++;
// Initialize first window
for (int i = 0; i < p.length(); i++) sf[s.charAt(i) - 'a']++;
// Check first window
if (Arrays.equals(pf, sf)) result.add(0);
// Slide the window
for (int i = p.length(); i < s.length(); i++) {
sf[s.charAt(i) - 'a']++; // Add new right char
sf[s.charAt(i - p.length()) - 'a']--; // Remove old left char
if (Arrays.equals(pf, sf)) {
result.add(i - p.length() + 1); // Start index of this window
}
}
return result;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().findAnagrams("cbaebabacd", "abc")); // [0, 6]
System.out.println(new Solution().findAnagrams("abab", "ab")); // [0, 1, 2]
}Step-by-Step Walkthrough
s = "cbaebabacd", p = "abc"
pf = {a:1, b:1, c:1}
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
First window s[0..2]="cba":
sf = {c:1, b:1, a:1} == pf → add index 0 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=3 (add 'e', remove 'c'):
sf = {b:1, a:1, e:1} ≠ pf
i=4 (add 'b', remove 'b'):
sf = {b:1, a:1, e:1} ≠ pf (no net change)
i=5 (add 'a', remove 'a'):
sf unchanged = {b:1, a:1, e:1} ≠ pf
i=6 (add 'b', remove 'e'):
sf = {b:2, a:1} ≠ pf
i=7 (add 'a', remove 'b'):
sf = {b:1, a:2} ≠ pf
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=8 (add 'c', remove 'a'):
sf = {b:1, a:1, c:1} == pf → add index 8-3+1=6 ✓
i=9 (add 'd', remove 'b'):
sf = {a:1, c:1, d:1} ≠ pf
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return [0, 6]Deep Insight
**Why Arrays.equals(pf, sf) is O(26) = O(1)?** Both arrays have exactly 26 elements (for lowercase English letters). Comparing two fixed-size arrays is O(26) = constant time. This makes each slide O(1) amortized.
**Connection to sw-10:** - sw-10: return true at first match (boolean) - sw-11: collect all matches (list of indices) Identical logic; only the return action differs.
**Optimization with `matches` counter (from sw-10):** Instead of calling `Arrays.equals` each time, maintain a `matches` counter (positions where pf[i]==sf[i]). When matches==26, add to result. This reduces the per-slide work from O(26) to O(1) operations: - When adding/removing a character, at most 2 positions in the freq arrays change. - Each position change affects `matches` by at most ±1.
**Edge cases:** - p longer than s: empty result - p equals s: one result at index 0 (if they're anagrams) - All same characters in p (e.g., p="aaa"): works correctly
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n × m) | O(m) | n windows × O(26) array comparison = O(26n) = O(n) |
| Optimal | O(n + m) | O(n + m) | O(m) for pf init + O(n) sliding; output list can be O(n) |
Pattern Recognition
✅ Find ALL positions where a fixed-size window matches a pattern ✅ Fixed window = p.length() ✅ Frequency array comparison (O(26) per slide) ✅ Identical to sw-10 but collects all results **LeetCode Trigger Phrases:** → "find all anagrams in a string" → "return all start indices of anagrams" → "rearrangements of p in s"
Bhagavad Gita 18.78
यत्र योगेश्वरः कृष्णो यत्र पार्थो धनुर्धरः। तत्र श्रीर्विजयो भूतिर्ध्रुवा नीतिर्मतिर्मम॥
Wherever there is Krishna, the lord of yoga, and wherever there is Arjuna, the wielder of the bow — there will certainly be prosperity, victory, glory, and righteousness.
Connection: The anagram algorithm finds every location in the text where the required combination of characters appears — just as Sanjaya declares that wherever the divine combination (Krishna + Arjuna) appears, victory follows. The algorithm collects all such appearances, not just the first. Completeness matters: every occurrence of the sacred combination must be found and honored, just as every anagrammatic blessing in Valmiki's Ramayana carries equal spiritual worth.