How to resolve Circular Dependency when one Helper class is depends on other Helper Class

Question

Having one module named Override\Search in which two helper classes are there.

1. Override\Search\Helper\Data.php 
2. Override\Search\Helper\Util.php

Both helper are depends on each other, thus giving circular dependency error.

Exception #0 (LogicException): Circular dependency: 

Try 1: - using their namespaces in header as follows but still facing same error:

use \Override\Search\Helper\Data as Override_MainHelper;

Try 2: - Adding initializing in constructor as below

public function __construct(
        //Other classes
        \Override\Search\Helper\Data $searchHelperMain
    ) {
        //Other classes
        $this->_searchHelperMain = $searchHelperMain;
    }

Following class is Main Data.php

<?php
namespace Override\Search\Helper;
use \Magento\Store\Model\StoreManagerInterface;
use \Magento\Backend\Model\Url;
use \Override\Search\Helper\Util;
use \Psr\Log\LoggerInterface;
use \Magento\Catalog\Model\Product;
use Magento\Config\Model\ResourceModel\Config\Data\Collection;
use \Magento\Framework\App\RequestInterface;

class Data extends \Magento\Framework\App\Helper\AbstractHelper
{
    /**
     * @var \Magento\Store\Model\StoreManagerInterface
     */
    protected $_storeModelStoreManagerInterface;
    /**
     * @var \Magento\Backend\Model\Url
     */
    protected $_backendModelUrl;
    /**
     * @var \Override\Search\Helper\Util
     */
    protected $_searchHelperConfig;
    /**
     * @var \Psr\Log\LoggerInterface
     */
    protected $_psrLogLoggerInterface;
    /**
     * @var \Magento\Catalog\Model\Product
     */
    protected $_catalogModelProduct;
    /**
     * @var \Magento\Tax\Helper\Data
     */
    protected $_taxHelperData;

    /**
     * @var \Magento\Eav\Model\Entity\Type
     */
    protected $_modelEntityType;

    /**
     * @var \Magento\Eav\Model\Entity\Attribute
     */
    protected $_modelEntityAttribute;

    /**
     * @var \Magento\Framework\Locale\CurrencyInterface
     */
    protected $_localeCurrency;

    /**
     * @var Magento\Directory\Model\CurrencyFactory
     */
    protected $_currencyFactory;

    /**
     * @var Magento\Config\Model\ResourceModel\Config\Data\Collection
     */
    protected $_configDataCollection;
    /**
     * @var \Magento\Store\Model\Store
     */
    protected $_frameworkModelStore;
    protected $_data_features_response;
    protected $_data_enabled_feature_response;
    public function __construct(
        \Magento\Store\Model\StoreManagerInterface $storeModelStoreManagerInterface,
        \Magento\Backend\Model\Url $backendModelUrl,
        \Override\Search\Helper\Util $searchHelperConfig,
        \Psr\Log\LoggerInterface $psrLogLoggerInterface,
        \Magento\Catalog\Model\Product $catalogModelProduct,
        \Magento\Catalog\Helper\Data $taxHelperData,
        \Magento\Eav\Model\Entity\Type $modelEntityType,
        \Magento\Eav\Model\Entity\Attribute $modelEntityAttribute,
        \Magento\Directory\Model\CurrencyFactory $currencyFactory,
        \Magento\Framework\Locale\CurrencyInterface $localeCurrency,
        \Magento\Config\Model\ResourceModel\Config\Data\Collection $configDataCollection
    ) {

        $this->_storeModelStoreManagerInterface = $storeModelStoreManagerInterface;
        $this->_backendModelUrl = $backendModelUrl;
        $this->_searchHelperConfig = $searchHelperConfig;
        $this->_psrLogLoggerInterface = $psrLogLoggerInterface;
        $this->_catalogModelProduct = $catalogModelProduct;
        $this->_taxHelperData = $taxHelperData;
        $this->_modelEntityType = $modelEntityType;
        $this->_modelEntityAttribute = $modelEntityAttribute;
        $this->_localeCurrency = $localeCurrency;
        $this->_currencyFactory = $currencyFactory;
        $this->_configDataCollection = $configDataCollection;
    }

   //Other Functions

}

Following class is Main Util.php

<?php
namespace Override\Search\Helper;

use \Magento\Framework\App\Config\ScopeConfigInterface;
use \Magento\Framework\UrlInterface;
use \Magento\Store\Model\StoreManagerInterface;
use \Override\Search\Model\Product\Sync;
use \Magento\Framework\Model\Store;
use \Override\Search\Model\Api\Action\Features;
use \Override\Search\Helper\Data;
//use \Override\Search\Helper\Data as Override_MainHelper;

class Util extends \Magento\Framework\App\Helper\AbstractHelper
{
    /**
     * @var \Override\Search\Helper\Data
     */
    protected $_searchHelperMain;

    public function __construct(
        //Other classes
        \Override\Search\Helper\Data $searchHelperMain
    ) {
        //Other classes
        $this->_searchHelperMain = $searchHelperMain;
    }

    //Other Functions

}

Having some idea about proxy and factories class but not sure what are pros and cons of those features except some lazy loading stuff and dependency injection.

http://alanstorm.com/magento_2_object_manager_proxy_objects

Circular dependency: Magento\Backend\Helper\Data depends on Magento\Backend\Model\Url and vice versa

https://devdocs.magento.com/guides/v2.3/extension-dev-guide/proxies.html

What is suitable here that can cover backward compatibility as well i.e. 2.1.x and 2.2.x and 2.3.x? Proxy or Factories or any 3rd way?