Problem

You are given an array of strings words and an integer k.

For each index i in the range [0, words.length - 1], find the length of the longest common prefix among any k strings (selected at distinct indices) from the remaining array after removing the ith element.

Return an array answer, where answer[i] is the answer for ith element. If removing the ith element leaves the array with fewer than k strings, answer[i] is 0.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: words = ["jump","run","run","jump","run"], k = 2
Output: [3,4,4,3,4]
Explanation:
* Removing index 0 (`"jump"`): 
* `words` becomes: `["run", "run", "jump", "run"]`. `"run"` occurs 3 times. Choosing any two gives the longest common prefix `"run"` (length 3).
* Removing index 1 (`"run"`): 
* `words` becomes: `["jump", "run", "jump", "run"]`. `"jump"` occurs twice. Choosing these two gives the longest common prefix `"jump"` (length 4).
* Removing index 2 (`"run"`): 
* `words` becomes: `["jump", "run", "jump", "run"]`. `"jump"` occurs twice. Choosing these two gives the longest common prefix `"jump"` (length 4).
* Removing index 3 (`"jump"`): 
* `words` becomes: `["jump", "run", "run", "run"]`. `"run"` occurs 3 times. Choosing any two gives the longest common prefix `"run"` (length 3).
* Removing index 4 ("run"): 
* `words` becomes: `["jump", "run", "run", "jump"]`. `"jump"` occurs twice. Choosing these two gives the longest common prefix `"jump"` (length 4).

Example 2

1
2
3
4

Input: words = ["dog","racer","car"], k = 2
Output: [0,0,0]
Explanation:
* Removing any index results in an answer of 0.

Constraints

  • 1 <= k <= words.length <= 10^5
  • 1 <= words[i].length <= 10^4
  • words[i] consists of lowercase English letters.
  • The sum of words[i].length is smaller than or equal 105.

Solution

Method 1 – Trie with Dynamic Frequency Tracking

Intuition

The key insight is to use a modified Trie data structure where each node tracks the frequency of words passing through it. We can efficiently determine the longest common prefix among k strings by maintaining a global frequency map and a sorted set of valid prefix lengths.

The strategy involves initially building a complete Trie with all words, then for each word removal, temporarily removing it from the Trie, checking the maximum valid prefix length, and reinserting it back.

Approach

  1. Enhanced Trie Structure: Create a Trie where each node contains a frequency counter representing how many words pass through that node.

  2. Global Tracking: Maintain a frequency map that counts how many prefix lengths have frequency ≥ k, and a descending-ordered set to quickly access the maximum valid prefix length.

  3. Initial Population: Insert all words into the Trie. During insertion, when a node’s frequency reaches k, increment the count for that prefix length in the global map and add it to the sorted set.

  4. Simulation Process: For each word to be “removed”:

    • Temporarily erase the word from the Trie
    • When a node’s frequency drops below k, decrement the corresponding length count in the map
    • If a length count reaches zero, remove it from the sorted set
    • Record the maximum valid prefix length (largest element in the set)
    • Reinsert the word back into the Trie

  5. Result Extraction: The maximum element in the sorted set gives the answer for each removal scenario.

Code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

class Solution {
private:
    map<int, int> lengthFreq;
    set<int, greater<int>> validLengths;
    
    struct TrieNode {
        TrieNode* children[26];
        int frequency;
        bool isEnd;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            frequency = 0;
            isEnd = false;
        }
        
        bool containsKey(char ch) {
            return children[ch - 'a'] != nullptr;
        }
        
        void put(char ch, TrieNode* node) {
            children[ch - 'a'] = node;
        }
        
        TrieNode* get(char ch) {
            return children[ch - 'a'];
        }
    };
    
    class Trie {
    public:
        TrieNode* root;
        
        Trie() {
            root = new TrieNode();
        }
        
        void insert(string& word, int k) {
            TrieNode* node = root;
            
            for (int i = 0; i < word.size(); i++) {
                if (!node->containsKey(word[i])) {
                    node->put(word[i], new TrieNode());
                }
                
                node = node->get(word[i]);
                node->frequency++;
                
                if (node->frequency >= k) {
                    lengthFreq[i + 1]++;
                    
                    if (lengthFreq[i + 1] == 1) {
                        validLengths.insert(i + 1);
                    }
                }
            }
            
            node->isEnd = true;
        }
        
        void erase(string& word, int k) {
            TrieNode* node = root;
            
            for (int i = 0; i < word.size(); i++) {
                node = node->get(word[i]);
                node->frequency--;
                
                if (node->frequency == k - 1) {
                    lengthFreq[i + 1]--;
                    
                    if (lengthFreq[i + 1] == 0) {
                        validLengths.erase(i + 1);
                    }
                }
            }
        }
    };
    
public:
    vector<int> longestCommonPrefix(vector<string>& words, int k) {
        lengthFreq.clear();
        validLengths.clear();
        
        Trie* trie = new Trie();
        vector<int> result;
        
        // Insert all words initially
        for (int i = 0; i < words.size(); i++) {
            trie->insert(words[i], k);
        }
        
        // Process each word removal
        for (int i = 0; i < words.size(); i++) {
            trie->erase(words[i], k);
            
            if (validLengths.empty()) {
                result.push_back(0);
            } else {
                result.push_back(*validLengths.begin());
            }
            
            trie->insert(words[i], k);
        }
        
        return result;
    }
};
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

class Solution {
    private Map<Integer, Integer> lengthFreq = new HashMap<>();
    private TreeSet<Integer> validLengths = new TreeSet<>(Collections.reverseOrder());
    
    class TrieNode {
        TrieNode[] children;
        int frequency;
        boolean isEnd;
        
        public TrieNode() {
            children = new TrieNode[26];
            frequency = 0;
            isEnd = false;
        }
        
        public boolean containsKey(char ch) {
            return children[ch - 'a'] != null;
        }
        
        public void put(char ch, TrieNode node) {
            children[ch - 'a'] = node;
        }
        
        public TrieNode get(char ch) {
            return children[ch - 'a'];
        }
    }
    
    class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode();
        }
        
        public void insert(String word, int k) {
            TrieNode node = root;
            
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (!node.containsKey(ch)) {
                    node.put(ch, new TrieNode());
                }
                
                node = node.get(ch);
                node.frequency++;
                
                if (node.frequency >= k) {
                    lengthFreq.put(i + 1, lengthFreq.getOrDefault(i + 1, 0) + 1);
                    
                    if (lengthFreq.get(i + 1) == 1) {
                        validLengths.add(i + 1);
                    }
                }
            }
            
            node.isEnd = true;
        }
        
        public void erase(String word, int k) {
            TrieNode node = root;
            
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                node = node.get(ch);
                node.frequency--;
                
                if (node.frequency == k - 1) {
                    lengthFreq.put(i + 1, lengthFreq.get(i + 1) - 1);
                    
                    if (lengthFreq.get(i + 1) == 0) {
                        validLengths.remove(i + 1);
                    }
                }
            }
        }
    }
    
    public int[] longestCommonPrefix(String[] words, int k) {
        lengthFreq.clear();
        validLengths.clear();
        
        Trie trie = new Trie();
        int[] result = new int[words.length];
        
        // Insert all words initially
        for (String word : words) {
            trie.insert(word, k);
        }
        
        // Process each word removal
        for (int i = 0; i < words.length; i++) {
            trie.erase(words[i], k);
            
            if (validLengths.isEmpty()) {
                result[i] = 0;
            } else {
                result[i] = validLengths.first();
            }
            
            trie.insert(words[i], k);
        }
        
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

from collections import defaultdict
import bisect

class TrieNode:
    def __init__(self):
        self.children = {}
        self.frequency = 0
        self.is_end = False

class Solution:
    def longestCommonPrefix(self, words: list[str], k: int) -> list[int]:
        self.length_freq = defaultdict(int)
        self.valid_lengths = []  # Will maintain in descending order
        
        class Trie:
            def __init__(self):
                self.root = TrieNode()
            
            def insert(self, word: str, k: int):
                node = self.root
                
                for i, char in enumerate(word):
                    if char not in node.children:
                        node.children[char] = TrieNode()
                    
                    node = node.children[char]
                    node.frequency += 1
                    
                    if node.frequency >= k:
                        self.length_freq[i + 1] += 1
                        
                        if self.length_freq[i + 1] == 1:
                            # Insert in descending order
                            bisect.insort(self.valid_lengths, -(i + 1))
                
                node.is_end = True
            
            def erase(self, word: str, k: int):
                node = self.root
                
                for i, char in enumerate(word):
                    node = node.children[char]
                    node.frequency -= 1
                    
                    if node.frequency == k - 1:
                        self.length_freq[i + 1] -= 1
                        
                        if self.length_freq[i + 1] == 0:
                            self.valid_lengths.remove(-(i + 1))
        
        trie = Trie()
        result = []
        
        # Insert all words initially
        for word in words:
            trie.insert(word, k)
        
        # Process each word removal
        for word in words:
            trie.erase(word, k)
            
            if not self.valid_lengths:
                result.append(0)
            else:
                result.append(-self.valid_lengths[0])  # Convert back from negative
            
            trie.insert(word, k)
        
        return result
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

import (
    "container/heap"
    "sort"
)

type TrieNode struct {
    children  [26]*TrieNode
    frequency int
    isEnd     bool
}

func NewTrieNode() *TrieNode {
    return &TrieNode{
        children:  [26]*TrieNode{},
        frequency: 0,
        isEnd:     false,
    }
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    return &Trie{root: NewTrieNode()}
}

func (t *Trie) insert(word string, k int, lengthFreq map[int]int, validLengths *[]int) {
    node := t.root
    
    for i, char := range word {
        index := char - 'a'
        if node.children[index] == nil {
            node.children[index] = NewTrieNode()
        }
        
        node = node.children[index]
        node.frequency++
        
        if node.frequency >= k {
            lengthFreq[i+1]++
            
            if lengthFreq[i+1] == 1 {
                // Insert in descending order
                length := i + 1
                pos := sort.Search(len(*validLengths), func(j int) bool {
                    return (*validLengths)[j] <= length
                })
                *validLengths = append(*validLengths, 0)
                copy((*validLengths)[pos+1:], (*validLengths)[pos:])
                (*validLengths)[pos] = length
            }
        }
    }
    
    node.isEnd = true
}

func (t *Trie) erase(word string, k int, lengthFreq map[int]int, validLengths *[]int) {
    node := t.root
    
    for i, char := range word {
        index := char - 'a'
        node = node.children[index]
        node.frequency--
        
        if node.frequency == k-1 {
            lengthFreq[i+1]--
            
            if lengthFreq[i+1] == 0 {
                length := i + 1
                for j, val := range *validLengths {
                    if val == length {
                        *validLengths = append((*validLengths)[:j], (*validLengths)[j+1:]...)
                        break
                    }
                }
            }
        }
    }
}

func longestCommonPrefix(words []string, k int) []int {
    lengthFreq := make(map[int]int)
    validLengths := make([]int, 0)
    
    trie := NewTrie()
    result := make([]int, len(words))
    
    // Insert all words initially
    for _, word := range words {
        trie.insert(word, k, lengthFreq, &validLengths)
    }
    
    // Process each word removal
    for i, word := range words {
        trie.erase(word, k, lengthFreq, &validLengths)
        
        if len(validLengths) == 0 {
            result[i] = 0
        } else {
            result[i] = validLengths[0]
        }
        
        trie.insert(word, k, lengthFreq, &validLengths)
    }
    
    return result
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

import java.util.*

class Solution {
    private val lengthFreq = mutableMapOf<Int, Int>()
    private val validLengths = TreeSet<Int>(Collections.reverseOrder())
    
    class TrieNode {
        val children = Array<TrieNode?>(26) { null }
        var frequency = 0
        var isEnd = false
        
        fun containsKey(ch: Char): Boolean {
            return children[ch - 'a'] != null
        }
        
        fun put(ch: Char, node: TrieNode) {
            children[ch - 'a'] = node
        }
        
        fun get(ch: Char): TrieNode? {
            return children[ch - 'a']
        }
    }
    
    inner class Trie {
        val root = TrieNode()
        
        fun insert(word: String, k: Int) {
            var node = root
            
            for (i in word.indices) {
                val ch = word[i]
                if (!node.containsKey(ch)) {
                    node.put(ch, TrieNode())
                }
                
                node = node.get(ch)!!
                node.frequency++
                
                if (node.frequency >= k) {
                    lengthFreq[i + 1] = lengthFreq.getOrDefault(i + 1, 0) + 1
                    
                    if (lengthFreq[i + 1] == 1) {
                        validLengths.add(i + 1)
                    }
                }
            }
            
            node.isEnd = true
        }
        
        fun erase(word: String, k: Int) {
            var node = root
            
            for (i in word.indices) {
                val ch = word[i]
                node = node.get(ch)!!
                node.frequency--
                
                if (node.frequency == k - 1) {
                    lengthFreq[i + 1] = lengthFreq[i + 1]!! - 1
                    
                    if (lengthFreq[i + 1] == 0) {
                        validLengths.remove(i + 1)
                    }
                }
            }
        }
    }
    
    fun longestCommonPrefix(words: Array<String>, k: Int): IntArray {
        lengthFreq.clear()
        validLengths.clear()
        
        val trie = Trie()
        val result = IntArray(words.size)
        
        // Insert all words initially
        for (word in words) {
            trie.insert(word, k)
        }
        
        // Process each word removal
        for (i in words.indices) {
            trie.erase(words[i], k)
            
            result[i] = if (validLengths.isEmpty()) {
                0
            } else {
                validLengths.first()
            }
            
            trie.insert(words[i], k)
        }
        
        return result
    }
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

use std::collections::{HashMap, BTreeSet};
use std::cmp::Reverse;

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    frequency: i32,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: Default::default(),
            frequency: 0,
            is_end: false,
        }
    }
    
    fn contains_key(&self, ch: char) -> bool {
        let index = (ch as u8 - b'a') as usize;
        self.children[index].is_some()
    }
    
    fn put(&mut self, ch: char, node: TrieNode) {
        let index = (ch as u8 - b'a') as usize;
        self.children[index] = Some(Box::new(node));
    }
    
    fn get_mut(&mut self, ch: char) -> &mut TrieNode {
        let index = (ch as u8 - b'a') as usize;
        self.children[index].as_mut().unwrap()
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }
    
    fn insert(&mut self, word: &str, k: i32, length_freq: &mut HashMap<i32, i32>, valid_lengths: &mut BTreeSet<Reverse<i32>>) {
        let mut node = &mut self.root;
        
        for (i, ch) in word.chars().enumerate() {
            if !node.contains_key(ch) {
                node.put(ch, TrieNode::new());
            }
            
            node = node.get_mut(ch);
            node.frequency += 1;
            
            if node.frequency >= k {
                let length = (i + 1) as i32;
                *length_freq.entry(length).or_insert(0) += 1;
                
                if length_freq[&length] == 1 {
                    valid_lengths.insert(Reverse(length));
                }
            }
        }
        
        node.is_end = true;
    }
    
    fn erase(&mut self, word: &str, k: i32, length_freq: &mut HashMap<i32, i32>, valid_lengths: &mut BTreeSet<Reverse<i32>>) {
        let mut node = &mut self.root;
        
        for (i, ch) in word.chars().enumerate() {
            node = node.get_mut(ch);
            node.frequency -= 1;
            
            if node.frequency == k - 1 {
                let length = (i + 1) as i32;
                *length_freq.get_mut(&length).unwrap() -= 1;
                
                if length_freq[&length] == 0 {
                    valid_lengths.remove(&Reverse(length));
                }
            }
        }
    }
}

impl Solution {
    pub fn longest_common_prefix(words: Vec<String>, k: i32) -> Vec<i32> {
        let mut length_freq: HashMap<i32, i32> = HashMap::new();
        let mut valid_lengths: BTreeSet<Reverse<i32>> = BTreeSet::new();
        
        let mut trie = Trie::new();
        let mut result = Vec::with_capacity(words.len());
        
        // Insert all words initially
        for word in &words {
            trie.insert(word, k, &mut length_freq, &mut valid_lengths);
        }
        
        // Process each word removal
        for word in &words {
            trie.erase(word, k, &mut length_freq, &mut valid_lengths);
            
            if valid_lengths.is_empty() {
                result.push(0);
            } else {
                result.push(valid_lengths.iter().next().unwrap().0);
            }
            
            trie.insert(word, k, &mut length_freq, &mut valid_lengths);
        }
        
        result
    }
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

class TrieNode {
    children: Map<string, TrieNode>;
    frequency: number;
    isEnd: boolean;
    
    constructor() {
        this.children = new Map();
        this.frequency = 0;
        this.isEnd = false;
    }
    
    containsKey(ch: string): boolean {
        return this.children.has(ch);
    }
    
    put(ch: string, node: TrieNode): void {
        this.children.set(ch, node);
    }
    
    get(ch: string): TrieNode | undefined {
        return this.children.get(ch);
    }
}

class Trie {
    root: TrieNode;
    
    constructor() {
        this.root = new TrieNode();
    }
    
    insert(word: string, k: number, lengthFreq: Map<number, number>, validLengths: number[]): void {
        let node = this.root;
        
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            
            node = node.get(ch)!;
            node.frequency++;
            
            if (node.frequency >= k) {
                const length = i + 1;
                lengthFreq.set(length, (lengthFreq.get(length) || 0) + 1);
                
                if (lengthFreq.get(length) === 1) {
                    // Insert in descending order
                    let insertIndex = 0;
                    while (insertIndex < validLengths.length && validLengths[insertIndex] > length) {
                        insertIndex++;
                    }
                    validLengths.splice(insertIndex, 0, length);
                }
            }
        }
        
        node.isEnd = true;
    }
    
    erase(word: string, k: number, lengthFreq: Map<number, number>, validLengths: number[]): void {
        let node = this.root;
        
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            node = node.get(ch)!;
            node.frequency--;
            
            if (node.frequency === k - 1) {
                const length = i + 1;
                lengthFreq.set(length, lengthFreq.get(length)! - 1);
                
                if (lengthFreq.get(length) === 0) {
                    const index = validLengths.indexOf(length);
                    if (index > -1) {
                        validLengths.splice(index, 1);
                    }
                }
            }
        }
    }
}

function longestCommonPrefix(words: string[], k: number): number[] {
    const lengthFreq = new Map<number, number>();
    const validLengths: number[] = [];
    
    const trie = new Trie();
    const result: number[] = [];
    
    // Insert all words initially
    for (const word of words) {
        trie.insert(word, k, lengthFreq, validLengths);
    }
    
    // Process each word removal
    for (const word of words) {
        trie.erase(word, k, lengthFreq, validLengths);
        
        if (validLengths.length === 0) {
            result.push(0);
        } else {
            result.push(validLengths[0]);
        }
        
        trie.insert(word, k, lengthFreq, validLengths);
    }
    
    return result;
}

Complexity

  • ⏰ Time complexity: O(n × L), where n is the number of words and L is the average word length. Each word is inserted and removed from the Trie twice, and each operation takes O(L) time.
  • 🧺 Space complexity: O(n × L), for storing the Trie structure with all unique prefixes and the additional data structures for frequency tracking.